Longest Common Subsequence

DSA · Intermediate

Definition

LCS finds the longest sequence appearing in both strings in order, not necessarily contiguous.

Basis of diff tools and edit-distance style DP.

Diagram

Flowchart

Example: LCS length

a, b = 'abcde', 'ace'
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a)):
    for j in range(len(b)):
        dp[i+1][j+1] = dp[i][j] + 1 if a[i] == b[j] else max(dp[i][j+1], dp[i+1][j])
print(dp[-1][-1])

Output: 3

Complexity

O(m × n)

Key points

Edit distance uses a similar table
Backtrack the table to print the sequence

Interview questions

Subsequence vs substring?

Substrings are contiguous; subsequences only keep order.