Loading...
Loading...
Loading...
Two product codes are strings of lowercase letters. A common subsequence is a string that can be made from each code by deleting some letters without changing the order of the rest. Print the length of the longest common subsequence.
Example 1
Input
abcde ace
Output
3
"ace" is the longest.
Example 2
Input
abc def
Output
0
Try the problem first. Open one hint at a time.
Let dp[i][j] be the answer for the first i letters of one code and the first j of the other.
Equal letters take the diagonal plus one. Otherwise take the larger of above and left.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor