Longest Common Subsequence
DSA · Dynamic Programming
Theory
The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same order, not necessarily contiguous. The DP table dp[i][j] holds the LCS length of the first i characters of one string and the first j of the other: if the characters match, dp[i][j] = dp[i-1][j-1] + 1, otherwise the maximum of dropping one character from either string. It runs in O(m × n).
Why we use it
LCS underlies diff tools, version control, DNA comparison and spell checking.
When to use it
Use LCS and related 2-D DP (edit distance) for text comparison, plagiarism detection, file diffs and sequence alignment.
How it works
- dp table (m+1) x (n+1) of zeros
- For each i, j
- a[i-1] == b[j-1]? Yes: dp[i][j] = dp[i-1][j-1] + 1. No: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- Return dp[m][n]
Syntax
dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise
Time: O(m·n) Space: O(m·n)Example
def lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 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])
out, i, j = [], m, n
while i and j:
if a[i - 1] == b[j - 1]:
out.append(a[i - 1]); i -= 1; j -= 1
elif dp[i - 1][j] >= dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[m][n], "".join(reversed(out))
print(lcs("ABCBDAB", "BDCABA"))
print(lcs("dynamic", "programming"))Key points
- Characters in order, not necessarily contiguous
- 2-D table over both prefixes
- Backtrack the table to recover the sequence
- O(m·n) time and space