Longest Common Subsequence
You get two strings a and b. They contain only lowercase English letters.
A subsequence of a string is what you get when you delete zero or more characters from it and keep the other characters in their original order. For example, "ace" is a subsequence of "abcde", but "aec" is not.
A common subsequence of a and b is a string that is a subsequence of both. Return the length of the longest common subsequence. If the two strings share no letter, return 0.
Hint
Let best[i][j] be the answer for the first i characters of a and the first j characters of b. If a[i - 1] equals b[j - 1], you can use that character: best[i][j] = best[i - 1][j - 1] + 1. If not, you must drop one of the two characters: take the larger of best[i - 1][j] and best[i][j - 1].
Examples
Example 1
- Input:
- "planet", "plant"
- Output:
- 5
"plant" is a subsequence of "planet" (delete the "e"), and it is the whole of "plant". So the answer is 5.
Example 2
- Input:
- "abcbdab", "bdcaba"
- Output:
- 4
"bcba" is a subsequence of both strings. No common subsequence of length 5 exists.
Example 3
- Input:
- "xyz", "abc"
- Output:
- 0
The two strings have no letter in common, so the only common subsequence is the empty string.
Constraints
0 <= a.length <= 400 <= b.length <= 40aandbcontain only lowercase English letters.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.