Longest Common
Subsequence
The problem: given two strings — here AGCAT and GAC — find the longest sequence of letters appearing in both, in the same order. The letters need not be next to each other.
The first three lessons all fit in a single row of cells. This one cannot, and the reason is worth more than the answer: a subproblem here is two positions at once — how far into each string — so it takes two numbers to name, and the table becomes a grid. Get that idea and edit distance, diff tools, and knapsack all stop looking new.
Play the game
Find the longest string of letters that appears in both "AGCAT" and "GAC", in order.
String A — tap letters to keep them (order is fixed)
String B — highlights show where your letters land
Discover the rule
Two prefixes, one comparison, two branches.
The last decision, in two strings at once
A subproblem here is a pair of prefixes: how far into A, and how far into B. So look at the last letter of each prefix. There are only two possibilities, and each one tells you what to do next.
Case 1 — the two prefixes end in the SAME letter
Both end in A. What should you do with that shared letter?
Finish beat 1 to unlock
Follow recursion
Two moving indices means many more ways to reach the same subproblem.
Recurrence
The rule says what an answer depends on:
L(i,j) = match ? L(i-1,j-1)+1 : max(L(i-1,j), L(i,j-1))Recursion
A match narrows to one call; a mismatch splits into two. So the tree is lopsided — read each node's shape rather than assuming it branches twice.
function lcs(i, j, a, b) {
if (i === 0 || j === 0) return 0;
if (a[i-1] === b[j-1]) return lcs(i-1, j-1, a, b) + 1;
return Math.max(lcs(i-1, j, a, b),
lcs(i, j-1, a, b));
}Run the recursive code for L(5,3). Tap a yellow call to reveal the calls it makes. Keep going until the tree is complete.
1 / 27 callsFinish beat 2 to unlock
Add memory
Cache on the pair, not on a single number.
One cache, two-part keys
Recursion still starts at the full problem, L(5,3), and works toward the empty prefixes. The only difference from the last three lessons is what a cache entry is keyed by: a pair of positions instead of a single index.
Current call stack
L(5,3)L(4,3)L(3,3)L(2,2)L(2,1)Top-down means we began with L(5,3) and followed its smaller dependencies.
Cache
The base cases start filled because their answers are already defined.
Decision 1 of 3
Recursion requests L(2,1). What should it do?
Finish beat 3 to unlock
Build bottom-up
Watch the grid fill, then take over the last row yourself.
New task: a grid instead of a row
Rows are prefixes of A
Row i means “the first i letters of AGCAT”. Row ∅ is the empty prefix.
Columns are prefixes of B
Column j means “the first j letters of GAC”. The corner cell is the answer.
Filling row by row means every cell's dependencies — above, left, and diagonal — already exist by the time you reach it. That is the whole reason bottom-up works.
Press start. The animation stops at every cell YOUR recurrence must fill.
Before you fill: the free row and column
Given base casesdp[0][j] = dp[i][0] = 0An empty prefix shares nothing with anything, so the entire top row and left column are zero.
The animation will fill the upper rows for you so you can watch the two branches alternate. It stops and asks you for the final row — including the corner cell, which is the answer you predicted in beat 2.
- 1
function lcs(a, b) { - 2
const dp = zeros(a.length + 1, b.length + 1); - 3
for (let i = 1; i <= a.length; i++) { - 4
for (let j = 1; j <= b.length; j++) { - 5
if (a[i-1] === b[j-1]) { - 6
dp[i][j] = dp[i-1][j-1] + 1; - 7
} else { - 8
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); - 9
} - 10
} - 11
} - 12
return dp[a.length][b.length]; - 13
}
Finish beat 4 to unlock
Make it transfer
Substrings, edit distance, and why this one needed two dimensions.
Variation 1: you want the longest common SUBSTRING (contiguous), not subsequence. What changes?
Variation 2: you want the minimum number of single-character inserts, deletes, and replacements to turn a into b (edit distance). How many buckets does a cell have?
Variation 3: why did this problem need a 2D table when climbing stairs, house robber, and coin change all managed with 1D?
Final check: four problems, four recurrences. What did you actually do the same way each time?
Finish beat 5 to unlock
The pattern, formally
The state: dp[i][j] is the LCS length of the first i characters of a and the first j of b. The recurrence: compare the last character of each prefix. If they are equal that pair can end the subsequence, so dp[i][j] = dp[i-1][j-1] + 1. If not, at least one of the two is unused, so try dropping each and keep the better: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base cases: dp[0][j] = dp[i][0] = 0. Time O(m × n), space O(m × n) and reducible to O(min(m, n)) by keeping only the previous row.
Naive recursion
Branch on every mismatch, all the way to the empty prefixes.
O(2^(m+n)) time
O(m + n) call stack
Memoization
Same branching, cached on the pair (i, j). Only visits the pairs it needs.
O(m × n) time
O(m × n) cache plus stack
Tabulation
One row-major sweep of the grid, no recursion at all.
O(m × n) time
O(m × n), reducible to one row
Takeaways
- A table has as many dimensions as it takes numbers to name a subproblem. Two positions, two dimensions. Nothing deeper than that.
- A matching pair is an addition with one dependency; a mismatch is a choice between two. The same cell can take either branch depending only on two characters.
- You cannot decide which character to drop on a mismatch, so you try both. That refusal to guess is what separates DP from a greedy heuristic.
- Filling the grid row by row guarantees the cells above, left, and diagonal are already written. Dependency order is a consequence of the recurrence, not a separate design choice.
- Memoization stores only the pairs the recursion actually reaches, which can be far fewer than the full grid. Tabulation fills all of them but avoids the call stack.
- Change the mismatch branch to reset to 0 and you have longest common substring. Add a third bucket for replacement and you have edit distance. The shape carries.