~/home/fill the grid, walk it back: longest common subsequence
Algorithm · Dynamic Programming
Fill the Grid, Walk It Back.
Don't memorize LCS — watch the table fill, then walk it backwards. The longest common subsequence of two strings grows one cell at a time: when the two characters match, the cell extends the diagonal by one; when they mismatch, it copies the better of the cell above or to the left. Fill the whole grid and the corner holds the length. Then backtrack from the corner along the diagonals to read off the actual subsequence.
match → diagonal + 1 · mismatch → max(up, left) · backtrack to recover
SUBSEQUENCE
Keep order, drop some characters (gaps allowed). LCS is the longest one shared by both strings.
DP TABLE
dp[i][j] = LCS length of the first i of A and first j of B. Empty prefixes are 0.
MATCH
If A[i−1] = B[j−1]: dp[i][j] = dp[i−1][j−1] + 1 — grow the diagonal.
MISMATCH
Else dp[i][j] = max(dp[i−1][j], dp[i][j−1]) — the best of dropping a char.
lcs.sim — A = ABCBDAB · B = BDCAB
Ready
Rows are A = ABCBDAB, columns B = BDCAB. Each cell is the LCS length of the prefixes that lead to it. Press Step: fill by the match / mismatch rule, then backtrack from the corner to recover the subsequence.
Dynamic programming turns an exponential search — there are 2ⁿ subsequences of a string — into a grid you fill once. Define dp[i][j] as the LCS length of the first i characters of A and the first j of B. An empty prefix shares nothing, so the top row and left column are all zero. Now every other cell follows from its three already-computed neighbours. If the newest characters A[i−1] and B[j−1] are equal, they can jointly end a longer subsequence, so the answer is one more than the diagonal cell: dp[i−1][j−1] + 1. If they differ, at least one of them is not used, so you take the better of ignoring A's last char (the cell above) or B's last char (the cell to the left). Two rules, filled row by row, and dp[n][m] is the length.
01
Define the subproblem
dp[i][j] = LCS length of prefixes A[0..i) and B[0..j). Base row and column are 0.
02
Match extends the diagonal
If the last characters are equal, that pair joins the LCS: dp[i][j] = dp[i−1][j−1] + 1.
03
Mismatch takes the max
Otherwise drop one character: dp[i][j] = max(dp[i−1][j], dp[i][j−1]).
04
Backtrack to recover
From the corner, step diagonally on matches (collecting the char), else toward the larger neighbour.
Time
O(n · m)
Space
O(n · m)
Length
dp[n][m]
String
Backtrack
The length only needs two rows at a time, so you can compute it in O(min(n, m)) space — but recovering the string itself wants the full grid (or the clever Hirschberg trick for linear space). LCS is the sibling of edit distance: the same table shape, one counting shared characters and the other counting edits. It powers diff tools, version-control merges, and DNA sequence alignment. Once you see this grid, the whole family of two-string DP problems reads the same way.
SOLVE IT YOURSELF
Solve it: longest common subsequence
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement lcs_length(a, b): return the length of the longest common subsequence of two strings (keep order, drop characters freely from each). Fill a 2-D table dp[i][j] = LCS length of the first i chars of a and first j of b. O(n·m).
HINTS — 4 IDEAS
Let dp[i][j] be the LCS length of a[:i] and b[:j]. An empty prefix gives 0, so row 0 and column 0 are all zero.
If the current characters match (a[i-1] == b[j-1]), extend the diagonal: dp[i][j] = dp[i-1][j-1] + 1.
Otherwise drop one character and take the better side: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
The answer is dp[n][m], the bottom-right corner.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · When A[i−1] = B[j−1], what is dp[i][j]?
A matching pair can end a subsequence one longer than the best for the two shorter prefixes, which sits on the diagonal.
2 · On a mismatch, the cell takes…
If the last characters differ, at least one is unused, so you keep the better of dropping A's last char (up) or B's last char (left).
3 · How do you recover the actual subsequence?
Each diagonal step on a match contributed a character; walking back from dp[n][m] and collecting those (in reverse) rebuilds one LCS.
Questions
Subsequence vs substring?
A subsequence keeps the original order but may skip characters (B_C_B from ABCBDAB); a substring must be contiguous. So the longest common subsequence is generally different from — and at least as long as — the longest common substring.
How does this relate to edit distance?
Same table shape. Edit distance counts insertions, deletions and replacements to convert A into B; LCS counts shared characters. With only insertions and deletions allowed, edit(A, B) = n + m − 2·LCS(A, B) — they are two views of one grid.
Can I save memory?
For the length alone, keep just the previous and current rows: O(min(n, m)) space. To reconstruct the string in linear space, use Hirschberg's divide-and-conquer method, which still runs in O(n·m) time.
One grid, every two-string DP.
Match grows the diagonal, mismatch keeps the best neighbour, and a walk back from the corner spells out the answer.