PreviousNext
Coding/Dynamic programming

Longest common subsequence

Write codeMedium25 minGoogle style

Your task

Return the length of the longest common subsequence of strings a and b. A subsequence keeps relative order but need not be contiguous; for example "abcde" and "ace" have LCS "ace" of length 3. Either string may be empty (answer 0). Strings can be up to ~1000 characters; an O(len(a)*len(b)) DP is expected, with O(min(len)) space achievable.

Examples

lcs_length(a: str, b: str) -> int
Example 1
Inputlcs_length("abcde", "ace")
Output3