Longest Common Subsequence

Given two strings, return the length of their longest common subsequence — characters that appear in the same relative order in both strings, not necessarily contiguous.

Example

Input: abcde, ace Output: 3 (the subsequence ace)

Approach

A 2D DP table where dp[i][j] is the LCS length using the first i characters of the first string and the first j of the second. If the characters match, extend the diagonal; otherwise take the best of dropping one character from either string.

Input format

Line 1: first string Line 2: second string

Print the LCS length.