Longest Common Subsequence

A subsequence of a string keeps some of its characters in their original order, though not necessarily side by side: "pto" is a subsequence of "python". Write lcs_length(a, b) that returns the length of the longest string that is a subsequence of both a and b.

Examples

lcs_length("python", "typhoon")  # returns 4
lcs_length("kitten", "sitting")  # returns 4
lcs_length("abc", "xyz")         # returns 0

"python" and "typhoon" share "thon" (and also "phon"), so the answer is 4.

Constraints

• 0 <= len(a), len(b) <= 1000