Longest Common Subsequence: The 2D DP Grid, Made Concrete
Longest Common Subsequence explained with a worked DP grid, JavaScript code, an O(n)-space rolling-row solution, complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Longest Common Subsequence is the problem that turns "dynamic programming" from a scary phrase into a mechanical grid you can fill in by hand. Give it two strings and it asks for the longest run of characters that appears in both, in the same order, but not necessarily contiguously.
The word that trips everyone is subsequence. It is not a substring. You are allowed to skip characters — delete any you like from either string — as long as the ones you keep stay in their original order. So ace is a subsequence of abcde, even though those letters are spread out.
Once you see LCS as a 2D table where every cell answers a smaller version of the same question, edit distance, diff tools, and DNA alignment all fall into place with the same machinery.
The problem
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
Input: text1 = "abcde", text2 = "ace"
Output: 3 // the LCS is "ace"
Input: text1 = "abc", text2 = "xyz"
Output: 0 // no shared characters at allTwo facts about the statement steer the whole solution:
- You return a length, not the actual subsequence — so you only need to track numbers, never rebuild strings.
- Order matters but adjacency does not —
acecounts even thougha,c, andeare not next to each other inabcde.
The brute force baseline
Walk both strings from the front. At each pair of positions (i, j), either the current characters match or they don't.
function lcs(text1, text2, i = 0, j = 0) {
if (i === text1.length || j === text2.length) return 0;
if (text1[i] === text2[j]) {
return 1 + lcs(text1, text2, i + 1, j + 1); // take both
}
return Math.max(
lcs(text1, text2, i + 1, j), // skip a char of text1
lcs(text1, text2, i, j + 1) // skip a char of text2
);
}This is correct but explodes. On a mismatch it branches into two recursive calls, and those branches re-solve the exact same (i, j) subproblems over and over. The running time is roughly O(2^(m+n)) — for two 20-character strings that is already a million-plus calls. The waste is pure repetition: the pair (3, 2) gets recomputed from dozens of different paths.
The key insight: every cell is a subproblem
The recursion only ever asks one kind of question — what is the LCS of text1[i:] and text2[j:]? There are only m × n distinct such questions, one per (i, j) pair. That is the definition of overlapping subproblems, and it is the signal to build a table instead of a call tree.
Define dp[i][j] = the LCS length of the first i characters of text1 and the first j characters of text2. The recurrence is short:
if text1[i-1] === text2[j-1]: dp[i][j] = 1 + dp[i-1][j-1] // match: pull the diagonal, add 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // mismatch: best of top / leftRead it spatially. A match means both strings just contributed a shared character, so you extend whatever LCS existed before both of them — the top-left diagonal neighbor — by one. A mismatch means you must drop one character from one string, so you inherit the better answer from above (skip this text1 char) or from the left (skip this text2 char). Row 0 and column 0 are all zeros, because matching anything against an empty string gives length 0.
The optimal solution
Filling the full m × n grid is O(m·n) time and O(m·n) space. But look at the recurrence: every cell only reads its own row and the row directly above it. You never need the rows before that. So keep just two rows — the previous one and the one you are building — and the space collapses to O(n), where n is the length of the string you put on the columns.
This is exactly what the visualizer runs:
function longestCommonSubsequence(text1, text2) {
// We only need two rows of the 2D DP matrix to save space O(min(m,n))
// We'll make text2 the columns
const n = text2.length;
let dpRow = new Array(n + 1).fill(0);
// Iterate through characters of text1
for (let i = 1; i <= text1.length; i++) {
let prevRow = dpRow;
dpRow = new Array(n + 1).fill(0);
// Iterate through characters of text2
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
// Characters match! Length is 1 + Top-Left Diagonal
dpRow[j] = 1 + prevRow[j - 1];
} else {
// Characters don't match. Max of Left or Top
dpRow[j] = Math.max(dpRow[j - 1], prevRow[j]);
}
}
}
return dpRow[n];
}The four moving parts map straight onto the recurrence: prevRow[j - 1] is the diagonal, prevRow[j] is the cell above, dpRow[j - 1] is the cell to the left (already computed this pass), and dpRow[j] is what you're filling. Each new row starts fresh as all zeros, which quietly rebuilds the "empty prefix = 0" base case for column 0. The answer is the last cell of the final row.
Walkthrough
Trace text1 = "abcde", text2 = "ace". Columns index the string _ a c e (the leading _ is the empty-prefix column, always 0). Each row below is one full pass of the outer loop — the dpRow after processing that character of text1.
| i | text1 char | prevRow | dpRow after pass | What happened |
|---|---|---|---|---|
| — | (init) | — | [0, 0, 0, 0] | Empty prefix of text1 vs everything → all 0 |
| 1 | a | [0,0,0,0] | [0, 1, 1, 1] | a===a → 1+diag at j=1; then max carries the 1 rightward |
| 2 | b | [0,1,1,1] | [0, 1, 1, 1] | b matches nothing → every cell inherits top/left |
| 3 | c | [0,1,1,1] | [0, 1, 2, 2] | c===c at j=2 → 1+prevRow[1]=1+1=2 |
| 4 | d | [0,1,2,2] | [0, 1, 2, 2] | d matches nothing → row copies down |
| 5 | e | [0,1,2,2] | [0, 1, 2, 3] | e===e at j=3 → 1+prevRow[2]=1+2=3 |
The answer is dpRow[3] = 3. Notice the three matches — a, then c, then e — each bump the running length by pulling the diagonal value forward, exactly in the order they appear in both strings. The b and d rows change nothing because those characters have no partner in ace; their job is just to carry the best-so-far numbers downward so the next match has the right diagonal to build on.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Naive recursion | O(2^(m+n)) | O(m+n) | branches on every mismatch, re-solves the same pairs |
| Full 2D table | O(m·n) | O(m·n) | one pass over every cell, whole grid retained |
| Rolling two rows | O(m·n) | O(n) | same cell count; only the previous row is ever read |
Time is fixed at O(m·n) for any table method — there are m × n cells and each costs O(1). Space is where the rolling version wins: because a cell only depends on its own row and the one above, two n+1-length arrays are enough. Put the shorter string on the columns and it becomes O(min(m, n)).
Common mistakes
- Confusing subsequence with substring. Substrings must be contiguous; subsequences can skip characters. LCS of
abcdeandaceis 3, not 1 — the letters need not be adjacent. - Taking
maxon a match. When characters match you must use1 + diagonal, notmax(top, left). Using max silently undercounts because it ignores the new shared character. - Reading the wrong neighbor. The diagonal is
prevRow[j - 1](previous row, previous column). GrabbingprevRow[j]ordpRow[j - 1]on a match is the classic off-by-one that produces answers that are close but wrong. - Forgetting the
+1dimension. The arrays are sizen + 1, and characters are indexed withtext1[i - 1]/text2[j - 1]. The extra slot at index 0 is the empty-prefix base case; drop it and every match reaches past the start of the array. - Reusing a dirty row. Each outer pass must start
dpRowas fresh zeros. Skip the reset and stale values from two characters ago leak into the new row.
Where this pattern shows up next
LCS is your entry point into the wider dynamic-programming toolkit — the "define a subproblem, write a recurrence, fill a table" method carries straight into these:
- Min Cost Climbing Stairs — the smallest possible 1D DP, where each state is
minof two prior steps. - House Robber — a take-it-or-skip-it recurrence, the linear cousin of LCS's match/mismatch choice.
- House Robber II — the circular twist that runs the House Robber DP twice.
- Coin Change — unbounded choices per state, showing DP beyond two neighbors.
You can also step through Longest Common Subsequence interactively to watch the grid fill in, the diagonal light up on matches, and the max flow down on mismatches, one cell at a time.
FAQ
What is the difference between a subsequence and a substring?
A substring is a contiguous slice — its characters sit next to each other in the original string. A subsequence keeps the original order but may skip characters, so ace is a subsequence of abcde but not a substring. Longest Common Subsequence uses the looser subsequence rule, which is exactly why the DP has to consider skipping characters from either string on a mismatch.
Why does the DP pull the diagonal on a match?
dp[i][j] is the LCS of the first i characters of text1 and the first j of text2. When those two ending characters are equal, they form a new shared pair that can be appended to the best LCS of everything before both of them — and "everything before both" is precisely the top-left diagonal cell dp[i-1][j-1]. Adding 1 records the newly matched character.
What is the time and space complexity of the LCS solution?
Time is O(m·n), where m and n are the two string lengths, because the algorithm evaluates every one of the m×n grid cells once with constant work each. The full-grid version uses O(m·n) space, but since each cell only depends on the current and previous rows, the rolling two-row version drops space to O(n) — or O(min(m, n)) if you place the shorter string on the columns.
Can I recover the actual subsequence, not just its length?
Yes, but you need the full 2D grid, not the two-row version. After filling dp, start at the bottom-right cell and walk backward: on a match step diagonally and prepend that character, otherwise move toward the larger of the top or left neighbor. That backtrace reconstructs one valid LCS. The space-optimized rolling-row solution discards the history that backtracking needs, so it can only report the length.
Does it matter which string I put on the rows versus the columns?
Not for the answer — LCS is symmetric, so lcs(a, b) equals lcs(b, a). It only matters for space. The rolling-row solution keeps arrays as long as the column string, so putting the shorter string on the columns makes the extra space O(min(m, n)) instead of O(max(m, n)). The visualizer puts text2 on the columns, matching the code above.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.