The Longest Common Subsequence (LCS) problem: find the longest sequence of characters that appears in the same order in both strings — not necessarily contiguously.
For example, ABCBDAB and BDCABA share the subsequence BCBA (length 4). It isn’t a substring of either, yet it appears in both, reading left to right.
This is the problem that powers diff, git merge, and DNA sequence alignment.
How It Works
The table dp[i][j] holds the LCS length of the first i characters of string A and the first j characters of string B:
- Initialize: the first row and column are 0 (an empty prefix shares nothing with anything).
- Match: if
A[i-1] == B[j-1], extend the diagonal result:dp[i][j] = dp[i-1][j-1] + 1. - Mismatch: otherwise carry the larger of the top and left neighbors:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - Reconstruct: walk the table from the bottom-right, following diagonals on matches.
Key Insight
The recurrence encodes a binary choice at every character pair:
- Diagonal moves include a character in the LCS.
- Up/left moves skip one.
Because any prefix’s best answer depends only on strictly smaller prefixes, filling row-by-row computes all answers — then a single backward walk recovers one concrete subsequence.
Worked Example
The visualizer runs the two strings A = ABCBDAB and B = BDCABA:
| ∅ | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| ∅ | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
The bottom-right cell reads 4, and the visualizer’s backtrack highlights B → C → B → A, yielding LCS = “BCBA”.
Edge Cases & Pitfalls
- One empty string — every row/column value is 0: the LCS is empty.
- Repeated characters — ties create multiple valid subsequences; backtracking picks one (e.g.
BDABis also valid here). - Subsequence ≠ substring — a substring is contiguous; LCS is order-only. Don’t mix up the two recurrences.
- Long inputs —
O(mn)memory for the full table. Length-only answers need justO(min(m, n))via two rolling rows.
Comparison: LCS vs Edit Distance
| Aspect | LCS | Edit distance |
|---|---|---|
| Question | Longest kept order | Fewest edits |
| Match cost | +1 | 0 |
| Mismatch | max(skip) | +1 (delete/insert/replace) |
| Relation | edits = m + n − 2·LCS (insert/delete only) | generalizes LCS |
Applications
- Version control —
diffandgit mergealign files as LCS-style sequences - Bioinformatics — DNA and protein sequence alignment
- Plagiarism detection — measuring document similarity
Practice Trajectory
- Hand-fill the table for two short strings and confirm the bottom-right value.
- Trace the backtrack to see why matches force a diagonal move.
- Distinguish LCS from the longest common substring recurrence.
- Reduce space to
O(min(m, n))for the length-only version. - Adapt the recurrence into edit distance and verify the
m + n − 2·LCSidentity.