Longest common subsequence

The problem it solves

Take two sequences — two versions of a file, two DNA strands, two users’ edit histories — and ask: what’s the longest thread common to both, keeping order but allowing gaps? That thread is the longest common subsequence, and it is the mathematical heart of diff: the lines your version-control system shows as “unchanged” are an LCS of the two files, and everything else becomes insertions and deletions. Bioinformatics runs on the same computation at scale — sequence alignment is LCS with a scoring system.

The word doing all the work is subsequence, not substring: characters must stay in order but need not be adjacent. "ace" is a subsequence of "abcde"; "aec" is not. Substring problems (contiguous) have different, often easier structure — misreading which one a problem is asking for is the fastest way to solve the wrong problem, so the distinction earns its bold type.

The intuition — and where it breaks down

Why is this hard? Greedy matching fails informatively: matching characters as early as possible in "abcbdab" vs "bdcaba" grabs matches that block better ones later — a locally good pairing can cost two matches downstream. The space of pairings is exponential, and no ordering trick rescues the greedy.

The dynamic-programming move is to stop trying to decide and instead enumerate answers to smaller questions. Define dp[i][j] = LCS length of the first i characters of A and the first j of B. Then look at the last characters of those prefixes: if they match, they can safely end the common thread — pair them, and the answer is one more than the answer for both prefixes shortened (dp[i-1][j-1] + 1). If they differ, at least one of them contributes nothing — so the answer is the better of dropping one: max(dp[i-1][j], dp[i][j-1]). Every cell answered by three earlier cells; the table fills row by row; the corner holds the answer to the original question.

The analogy people reach for — “it’s like filling in a spreadsheet” — is true but toothless, because it doesn’t say why the recurrence is safe. The real content is the match case: why is pairing matching last characters never a mistake? Because if some optimal thread doesn’t use this pairing, it uses each of these characters at most once elsewhere — and swapping to pair them here never shortens the thread (an exchange argument). That’s the sentence to internalize; the spreadsheet is just where the sentence gets applied n·m times.

Loading…

A walkthrough you can check

A = "bd", B = "abd" — small enough to hold entirely in your head. The table is 3×4 (a row and column of zeros for empty prefixes).

• Row b: against prefix "a" — no match, both neighbours zero → 0. Against "ab" — last chars b=b match: diagonal (0) + 1 → 1. Against "abd" — b vs d, no match: max(above=0… left=1) → 1.
• Row d: against "a" → 0. Against "ab": d vs b, max(1, 0) → 1. Against "abd": d=d match: diagonal (1) + 1 → 2.

Corner: 2 — the thread "bd". Now the part most presentations skip: the thread itself is recovered by walking backwards from the corner — at a match cell, the character was used: emit it, step diagonally; otherwise step to whichever neighbour supplied the max. The visualization runs this reconstruction at the end and lights the diagonal steps; the prediction prompts mid-fill ask you to compute a cell before it’s written and to name which neighbour feeds a match (always the diagonal — the only neighbour that consumes a character from both strings).

The invariant

Every filled cell dp[i][j] is exactly the LCS length of the two prefixes it names — not an estimate, the true answer to a smaller instance of the whole problem. The fill order (row by row) exists purely to serve the dependency arrows: each cell needs its upper, left, and upper-left neighbours already true. Any order respecting those arrows works — column-major, anti-diagonals (which parallelize) — and seeing that the order is incidental while the dependencies are essential is the moment DP stops being “fill tables” and starts being “solve subproblems”.

The repo checks the invariant the honest way: every cell is written exactly once (tested), every interior cell records which neighbour fed it (drawn as arrows in the visualization), and the reconstruction path’s length equals the corner value (tested).

Complexity, derived

n·m cells, O(1) work each: O(nm) time, and the trace’s step count is asserted to grow quadratically on square inputs. Space is O(nm) for the full table — but each row depends only on the previous row, so length-only answers fit in O(min(n, m)) with two rolling rows. The catch worth saying before it’s asked: rolling rows destroy the backwards walk, so reconstruction seems to need the full table — unless you know Hirschberg’s trick (divide-and-conquer on the middle row) which recovers the sequence in linear space at 2× time. Name it; deriving it is rarely demanded.

Two neighbouring identities put LCS at the centre of a small family: edit distance with only insert/delete allowed is n + m − 2·LCS (everything off-thread must be deleted or inserted), and longest common substring (contiguous) uses the same table with the no-match case reset to zero — one changed line, different problem. Recognizing family members from the recurrence is the durable skill.

What people get wrong

Substring vs subsequence. Worth repeating because the failure is total: the contiguous version’s answer lives at the table’s maximum, not its corner, and the recurrence differs in one clause.

Off-by-one between string indices and table indices. The table has an extra row and column for empty prefixes; dp[i][j] compares A[i-1] with B[j-1]. Fusing the two indexings produces boundary reads and subtly wrong corners — the classic transcription bug of this entire problem class.

Reconstructing forwards. The choices flow backwards from the corner; a forward walk can’t know which option each cell actually took. If you need the thread, walk from the end.

Taking the diagonal on a mismatch. The diagonal shortcut belongs to matches only — it’s the case that consumes a character from each string. Allowing it on mismatches invents an operation (free substitution) that LCS doesn’t have; that’s edit distance’s recurrence leaking in.

Implementation notes across languages

Python: the two-row form is prev, curr = curr, prev swapping lists — allocate once, never inside the loop; and functools.cache on the recursive form works for small inputs but hits recursion limits near n·m ≈ 10⁶, where the iterative table just works. Java/C++: int[][] dp = new int[n+1][m+1] — zero-initialized by the language, which quietly handles the base row and column; in C++, a single vector of size (n+1)·(m+1) with manual indexing measurably beats vector-of-vectors on large inputs (cache lines). JavaScript: beware Array(n).fill(Array(m)) — it aliases one row n times, the most common JS DP bug in existence; use Array.from({length: n}, () => new Array(m).fill(0)). Everywhere: for real diffing, production tools use Myers’ algorithm — O((n+m)·d) in the edit distance d — because real diffs are small; knowing that LCS-the-table is the concept and Myers is the practice is the engineering coda.