Longest Common Subsequence
mediumDynamic Programming+20 XPTime limit 4s
A subsequence keeps some characters of a string in their original order (ace is a subsequence of abcde). Find the length of the longest subsequence common to both strings.
Input:
- line 1:
a - line 2:
b
Output: the length of their longest common subsequence.
Constraints: 1 ≤ length of a, b ≤ 1000; lowercase letters.
Think about it: the classic 2-D DP — dp[i][j] = LCS of the first i characters of a and the first j of b. If the characters match, dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]). The same table drives diff tools and DNA alignment.
Sample input 1
abcde ace
Sample output 1
3
Sample input 2
abc abc
Sample output 2
3
Sample input 3
abc def
Sample output 3
0
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).