237. Longest Common Subsequence
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.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.