Two product catalogs each encode their item ordering as a string of lowercase letters. To measure how aligned the two orderings are, compute the length of their longest common subsequence: the greatest number of characters that appear in both strings in the same relative order (not necessarily contiguously).
Line 1: the first catalog string a.
Line 2: the second catalog string b.
A single integer: the length of the longest common subsequence of a and b.
a <= 40b <= 40Example 1
Input
abcbdab bdcaba
Expected
4
Explanation
One longest common subsequence is bcba (length 4); no common subsequence is longer, so the answer is 4.
Example 2
Input
abc abc
Expected
3
Explanation
The strings are identical, so the whole string is common: length 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →