237. Longest Common Subsequence
Challenge1000 ms256 MBSolved by 0%
Given two strings, print the length of the longest sequence of characters appearing in both in the same order. The characters need not be adjacent.
abcde and ace -> 3 (a, c, e)
Compare the last character of each. If they match, that character can be part of the answer and the problem shrinks on both sides. If they do not, the answer is the better of dropping the last character of one string or the other.
Written plainly that branches twice per call. Two different paths reach the same pair of positions constantly, which is what makes it fast once stored.
Constraints - `1 ≤ length of a ≤ 2000` - `1 ≤ length of b ≤ 2000` - Both strings are lowercase letters.
Input
The first line contains the string a.
The second line contains the string b.
Both consist of lowercase letters.
Output
Print one integer, the length of the longest common subsequence.
Inputabcde
ace
Output3
Noteis the worked example, with the answer spread out
Inputabc
def
Output0
Notehas nothing in common, so the answer is 0
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution