Longest Common Subsequence

Compute the length of the longest common subsequence between two strings.

dynamic-programming strings lcs subsequence

Write a function `longest_common_subsequence(s1: str, s2: str) -> int` that returns the length of the longest subsequence common to both strings. A subsequence is a sequence derived from a string by deleting zero or more characters without changing the order of the remaining characters. For example, "abc" is a subsequence of "abdc", but "acb" is not. The function should handle empty strings and strings with different lengths. The solution must use dynamic programming and run in O(len(s1) * len(s2)) time and O(len(s1) * len(s2)) space.

Constraints

0 <= len(s1), len(s2) <= 1000. Strings consist of lowercase English letters only. The answer fits in a 32-bit integer.

Example

>>> longest_common_subsequence("abcde", "ace")
3
>>> longest_common_subsequence("abc", "abc")
3
>>> longest_common_subsequence("abc", "def")
0
>>> longest_common_subsequence("", "abc")
0

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about building a 2D table where dp[i][j] represents the LCS length of s1[:i] and s2[:j].

If the current characters match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise, take the maximum of dp[i-1][j] and dp[i][j-1].

The answer will be at dp[len(s1)][len(s2)].

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.