Longest Common Subsequence

Hard · rating 1700 · dp, strings

Read two lines, strings a and b. Print the length of their longest common subsequence (characters need not be contiguous but must keep order).

Constraints: 1 ≤ |a|, |b| ≤ 1000

Editorial

Approach (2D dynamic programming)

Let dp[i][j] be the LCS length of the first i characters of a and first j of b. If the current characters match, extend the diagonal: dp[i-1][j-1] + 1. Otherwise take the better of dropping one character from either string: max(dp[i-1][j], dp[i][j-1]).

for i in range(1, len(a)+1):
    for j in range(1, len(b)+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[len(a)][len(b)]

Complexity

Time: O(n × m). Space: O(n × m), reducible to O(min(n, m)).

Open Longest Common Subsequence in Code Arena →