On this page
Description
Take two sequences: two versions of a file, two DNA strands, two words. What do they have in common, in the same order, allowing gaps? That's the longest common subsequence (LCS). Comparing every subsequence of one against the other is exponential. The DP state that makes it manageable is a pair of prefixes: dp[i][j] is the LCS of the first i items of one and the first j of the other.
We'll go from simple to more technical:
- The pattern: a padded (m + 1) × (n + 1) table, where a match goes diagonal and a mismatch takes the better neighbor.
- A second flavor: reductions such as palindromes, deletions and the shortest common supersequence.
- Where LCS runs in production (diffs, version control, bioinformatics).
- What breaks it: substring vs subsequence, padded indexing, aliased rows, memory.
The approach
Java
int longestCommonSubsequence(String a, String b) {
int m = a.length(), n = b.length();
int[][] dp = new int[m + 1][n + 1]; // dp[i][j] = LCS of a[0..i) and b[0..j)
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1; // last characters match: take them together
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // drop the last character of one side
}
}
}
return dp[m][n];
}
Python
def longest_common_subsequence(a: str, b: str) -> int:
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)] # dp[i][j] = LCS of a[:i] and b[:j]
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 # last characters match: take them together
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # drop the last character of one side
return dp[m][n]
Row 0 and column 0 stand for empty prefixes (LCS 0), so dp[i][j] reads a.charAt(i - 1) and b.charAt(j - 1) - the off-by-one that makes the base case free. If the last characters match, using them together is always safe; if not, one of them isn't in the LCS, so drop it from one side or the other and take the better result. Each row only reads the row above, so two rows (O(min(m, n)) space) are enough for the length.
A second flavor: a palindrome is a common subsequence with its reverse
The longest palindromic subsequence of s reads the same forwards and backwards, so it's a subsequence of both s and reverse(s) - and the longest common subsequence of those two is exactly it:
Java
int longestPalindromeSubseq(String s) {
return longestCommonSubsequence(s, new StringBuilder(s).reverse().toString());
}
Python
def longest_palindrome_subseq(s: str) -> int:
return longest_common_subsequence(s, s[::-1])
For "bbbab" that's 4 ("bbbb"). The same reduction answers other questions: the fewest deletions to make two strings equal is m + n - 2 * LCS, and the shortest string containing both as subsequences has length m + n - LCS.
Where you'll see it
diff and version-control merges start from the common subsequence of two files' lines; everything outside it is reported as insertions and deletions. Bioinformatics aligns DNA and protein sequences with the same two-prefix table (with scores instead of +1). Plagiarism and near-duplicate detection compare token sequences the same way.
Which tool for which job?
| You need | Use |
|---|---|
| The LCS length | the DP with two rows, O(min(m, n)) space |
| The LCS itself | the full table and a walk back, or Hirschberg for linear space |
| Longest palindromic subsequence | LCS of s and reverse(s) |
| Fewest deletions to make two strings equal | m + n - 2 × LCS |
| A diff of two similar files | Myers' algorithm, O((m + n) × D) |
| LCS when one sequence has no repeats | LIS of positions, O(n log n) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Treating it as substring | "grape" vs "gate" gives 1 instead of 3 | on a mismatch, take the better neighbor |
| Indexing chars by table position | off by one | cell (i, j) compares chars i - 1 and j - 1 |
[[0] * (n + 1)] * (m + 1) in Python | one shared row: LCS("abc", "aaa") gives 3, not 1 | a list comprehension |
| A full table for the length only | 400 MB for two 10,000-letter strings | two rows |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. What's the LCS of "grape" and "gate", and what's their longest common substring?
Show answer
LCS 3 ("gae" - gaps allowed), longest common substring 1 (no two neighboring letters of one appear side by side in the other). The subsequence recurrence skips characters on a mismatch; the substring one resets to 0.
2. Why does the table have an extra row and column, and how does that affect indexing?
Show answer
Row 0 and column 0 represent empty prefixes, whose LCS is 0 - so no special-case code is needed for them. The price is that cell (i, j) covers prefixes of length i and j, whose last characters are at charAt(i - 1) and charAt(j - 1).
3. How do you get the longest palindromic subsequence from an LCS routine?
Show answer
Compute LCS(s, reverse(s)). A palindromic subsequence reads the same both ways, so it's common to s and its reverse; the longest common one is the longest palindrome. For "bbbab" it's 4.
Key takeaways
- Two-sequence DP: dp[i][j] describes the first i items of one and the first j of the other.
- Match: extend the diagonal by 1. Mismatch: the best of dropping one character from either side.
- Padded row/column 0 = empty prefixes; cell (i, j) compares characters i - 1 and j - 1.
- Two rows give the length in O(min(m, n)) space; reconstruction needs the full table.
- Many problems reduce to LCS: palindromic subsequence, minimum deletions, shortest common supersequence.