Longest common subsequence
Pick some letters of a string, keep them in the order they appear, and read them off: the result is a subsequence of that string. Gaps are allowed, but the order is not changed. For example, "pig" is a subsequence of "spring" (skip the s, the r and the n), but "gip" is not, because in "spring" the g comes after the i and the p.
You get two strings, first and second. Return the length of the longest string that is a subsequence of both. When no letter appears in both strings, the answer is 0.
first = "spring", second = "pigs"Output3The longest common subsequence is "pig". The s cannot join it: in "spring" it comes before the p, in "pigs" after the g.
first = "rabbit", second = "habit"Output4"abit": skip the r and one b of "rabbit", and the h of "habit".
first = "cat", second = "dog"Output0No letter appears in both.
1 ≤ len(first), len(second) ≤ 1,000
Both strings use only lowercase English letters.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.