Longest Common Subsequence

A subsequence of a string $X = x_1 x_2 \dots x_m$ is any sequence obtainable by deleting zero or more characters from $X$ without reordering the remaining ones. For example, `ACE` is a subsequence of `ABCDE`, but `AEC` is not, since it violates the original order. Given two strings $X$ (length $m$) and $Y$ (length $n$), the Longest Common Subsequence problem asks for a longest string $Z$ that is a subsequence of both $X$ and $Y$. Note carefully: $Z$ need not be contiguous in either string — that distinct, harder problem is the longest common substring, and confusing the two is a classic error. The crucial structural fact is optimal substructure: if $Z = z_1 \dots z_k$ is an LCS of $X$ and $Y$, then:

• If $x_m = y_n$, then $z_k = x_m = y_n$, and $z_1 \dots z_{k-1}$ is an LCS of $X_{m-1} = x_1\dots x_{m-1}$ and $Y_{n-1} = y_1 \dots y_{n-1}$.
• If $x_m \neq y_n$, then $Z$ is a common subsequence of $X_{m-1}, Y$ or of $X, Y_{n-1}$ (at least one, possibly both), and it must be the longer of the two best such subsequences.

This is the exact same style of reasoning used in Introduction to Dynamic Programming: a problem on the full input reduces to a problem on strictly smaller sub-inputs, and the sub-inputs overlap enormously — the prefix pair $(i,j) = (3,5)$ is reused by many different recursive paths from $(m,n)$. That overlap is what separates DP from plain divide-and-conquer, and it is what makes memoization versus tabulation a meaningful design choice rather than an afterthought.

Define $c[i][j]$ as the length of an LCS of the prefixes $X_i = x_1 \dots x_i$ and $Y_j = y_1 \dots y_j$, for $0 \le i \le m$, $0 \le j \le n$. The base cases are $c[0][j] = 0$ for all $j$ and $c[i][0] = 0$ for all $i$, since an empty prefix has no common subsequence with anything except the empty string. The recurrence formalizes the substructure argument above:

Tabulation fills this table in increasing order of $i$ and $j$, so that by the time we need $c[i-1][j-1]$, $c[i-1][j]$, and $c[i][j-1]$, all three are already computed. The answer to the whole problem is $c[m][n]$. To recover the actual subsequence (not merely its length), we record, alongside each cell, which case produced it — a "direction" pointer — and then walk backward from $(m, n)$ to $(0, 0)$: whenever a diagonal move was taken (a match), we emit that character; whenever an up or left move was taken, we simply move without emitting anything. Because we walk backward, the emitted characters come out in reverse order and must be reversed once at the end. ``` function LCS-LENGTH(X, Y): m = length(X) n = length(Y) let c[0..m][0..n] be a new table // c[i][j] = LCS length of X[1..i], Y[1..j] let b[0..m][0..n] be a new table // direction: DIAG, UP, or LEFT for i = 0 to m: c[i][0] = 0 for j = 0 to n: c[0][j] = 0 for i = 1 to m: for j = 1 to n: if X[i] == Y[j]: c[i][j] = c[i-1][j-1] + 1 b[i][j] = DIAG else if c[i-1][j] >= c[i][j-1]: c[i][j] = c[i-1][j] b[i][j] = UP else: c[i][j] = c[i][j-1] b[i][j] = LEFT return c[m][n], b

function BUILD-LCS(b, X, i, j): result = empty list while i > 0 and j > 0: if b[i][j] == DIAG: append X[i] to result i = i - 1 j = j - 1 else if b[i][j] == UP: i = i - 1 else: j = j - 1 reverse(result) return result ``` The `LCS-LENGTH` procedure is pure tabulation — bottom-up filling in an order that respects dependencies — versus the equally valid alternative of top-down memoized recursion on `(i, j)` pairs, which computes exactly the same values on demand and caches them. Both realize the identical recurrence; tabulation is typically preferred here because the dependency structure (a full rectangular grid, no missing cells) means we will need essentially every entry anyway, so there is no time saved by laziness, and iteration avoids recursion-stack overhead.

Time complexity. The nested loop structure visits each of the $(m+1)(n+1)$ cells exactly once, and each cell does $O(1)$ work — one comparison and one constant-time recurrence evaluation. Hence

This is exponentially better than the brute-force $O(2^m \cdot n)$ approach of enumerating subsequences of $X$ and checking each against $Y$. Backtracking to reconstruct the string takes $O(m+n)$ time, since each step of the walk decreases $i$, $j$, or both by one, so the path length is bounded by $m+n$.

Space complexity. Storing the full tables $c$ and $b$ costs $\Theta(mn)$ space. If only the length of the LCS is required, not the subsequence itself, this can be compressed to $O(\min(m,n))$ by keeping only two rows (or columns) of $c$ at a time, since row $i$ depends only on row $i-1$ and itself. This is the same rolling-array trick applicable to many DP recurrences with a narrow dependency band. The tradeoff is real: with only two rows retained, the backtracking pointers are gone, and reconstructing the actual sequence would require either recomputing sub-tables (Hirschberg's algorithm achieves $O(m+n)$ space with full reconstruction, at roughly double the time constant) or falling back to the full $O(mn)$ table.

Correctness. The proof is a direct induction on $i + j$, mirroring the optimal-substructure argument. Base case: $c[i][0] = c[0][j] = 0$ for all $i, j$, since the empty string shares no nonempty subsequence with anything. Inductive step: assume $c[i'][j']$ is correctly the LCS length of $X_{i'}$, $Y_{j'}$ for all $i' + j' < i+j$. Consider $c[i][j]$.

• If $x_i = y_j$: any common subsequence of $X_i, Y_j$ that does not end by matching $x_i$ with $y_j$ can be shown to be no longer than one that does (a standard exchange argument — if an LCS $Z$ omits using this final matching pair, we can always extend it or find an equally long alternative that uses it, because the last characters are identical and available in both prefixes). Hence the LCS of $X_i, Y_j$ is exactly the LCS of $X_{i-1}, Y_{j-1}$ extended by this shared character, giving $c[i][j] = c[i-1][j-1] + 1$.
• If $x_i \neq y_j$: an LCS of $X_i, Y_j$ cannot use both $x_i$ and $y_j$ as its final aligned pair (they are unequal), so it either ignores $x_i$ (giving a common subsequence of $X_{i-1}, Y_j$) or ignores $y_j$ (giving one of $X_i, Y_{j-1}$) — possibly both are ignorable, but at least one must be, since the LCS's last character is some single symbol that cannot simultaneously be "the unused $x_i$" and "the unused $y_j$" while both remain unused. Taking the better of the two smaller subproblems, $c[i][j] = \max(c[i-1][j], c[i][j-1])$, is therefore correct and cannot overcount.

By induction, $c[m][n]$ is exactly the LCS length of $X$ and $Y$. The backtracking procedure follows recorded directions that correspond precisely to the case applied at each cell, so it reconstructs a string of length $c[m][n]$ that is by construction a common subsequence — establishing both feasibility and optimality.

Honest tradeoffs. LCS's $O(mn)$ time is worst-case tight for the standard DP: no algorithm faster than roughly quadratic time is known for general alphabets under the mild computational assumptions used in fine-grained complexity theory (there is a conditional lower bound tying LCS to the Strong Exponential Time Hypothesis, meaning a truly subquadratic algorithm for all inputs would be a major breakthrough). Faster algorithms exist for special cases: bounded alphabets, few matches, or when the answer is known to be short (e.g., Hunt–Szymanski-style techniques using the number of matching pairs). For most practical purposes — diff tools, bioinformatics — the plain $O(mn)$ table is the right tool, and its simplicity is a genuine advantage over cleverer but fragile alternatives.

Let $X = \texttt{ABCBDAB}$ ($m=7$) and $Y = \texttt{BDCAB}$ ($n=5$). We build $c[i][j]$ for $i=0,\dots,7$ and $j=0,\dots,5$. Row/column $0$ are all zero. Filling row by row (showing the interesting rows):

Trace the two cells that most reward attention:

• $c[3][3]$: $X[3] = \texttt{C}$, $Y[3] = \texttt{C}$ — they match, so $c[3][3] = c[2][2] + 1 = 1 + 1 = 2$.
• $c[6][4]$: $X[6] = \texttt{A}$, $Y[4] = \texttt{A}$ — match, so $c[6][4] = c[5][3] + 1 = 2 + 1 = 3$.
• $c[2][1]$: $X[2]=\texttt{B}$, $Y[1]=\texttt{B}$ — match, $c[2][1] = c[1][0]+1 = 0+1=1$.
• $c[5][1]$: $X[5]=\texttt{D}$, $Y[1]=\texttt{B}$ — mismatch, $c[5][1] = \max(c[4][1], c[5][0]) = \max(1,0) = 1$.

The final answer, $c[7][5] = 4$, is the LCS length.

Backtracking from $(7,5)$: 1. $(7,5)$: $X[7]=\texttt{B}$, $Y[5]=\texttt{B}$ — match. Emit `B`. Move to $(6,4)$. 2. $(6,4)$: $X[6]=\texttt{A}$, $Y[4]=\texttt{A}$ — match. Emit `A`. Move to $(5,3)$. 3. $(5,3)$: $X[5]=\texttt{D}$, $Y[3]=\texttt{C}$ — mismatch. $c[4][3]=2$, $c[5][2]=2$ — tie, take UP (a valid tie-break). Move to $(4,3)$. 4. $(4,3)$: $X[4]=\texttt{B}$, $Y[3]=\texttt{C}$ — mismatch. $c[3][3]=2 \ge c[4][2]=1$, move UP to $(3,3)$. 5. $(3,3)$: $X[3]=\texttt{C}$, $Y[3]=\texttt{C}$ — match. Emit `C`. Move to $(2,2)$. 6. $(2,2)$: $X[2]=\texttt{B}$, $Y[2]=\texttt{D}$ — mismatch. $c[1][2]=0$, $c[2][1]=1$ — take LEFT, move to $(2,1)$. 7. $(2,1)$: $X[2]=\texttt{B}$, $Y[1]=\texttt{B}$ — match. Emit `B`. Move to $(1,0)$. 8. $i=1, j=0$: loop stops (`j = 0`). Emitted in reverse pop order `B, A, C, B` → reverse → `BCAB`, a valid LCS of length 4. (Note `BDAB` is not a common subsequence check target here — `BCAB` is confirmed: it is a subsequence of `ABCBDAB` at positions 2,3,4? Let's verify directly: `A-B-C-B-D-A-B`, picking positions 2(B),3(C),6(A),7(B) gives `B,C,A,B` = `BCAB` ✓, and in `Y=BDCAB` picking positions 1(B),3(C),4(A),5(B) gives `B,C,A,B` = `BCAB` ✓.)

The LCS problem sits at the intersection of combinatorics on words, computational biology, and the broader development of dynamic programming as a paradigm. Dynamic programming itself was formalized by Richard Bellman in the 1950s while working on multistage decision processes at the RAND Corporation; Bellman's "principle of optimality" — that an optimal solution to a problem contains optimal solutions to its subproblems — is exactly the property LCS exploits when reasoning about prefixes. The specific application to comparing biological sequences and text became prominent through the 1970s, driven by the practical need to align DNA and protein sequences and to build efficient file-comparison tools; the Unix `diff` utility and its descendants are direct engineering applications of LCS-style alignment.

Version-control systems such as Git and Subversion compute file diffs using LCS-style alignment: the "unchanged" lines of two file versions form a longest common subsequence, and everything else is displayed as an insertion or deletion around it. Bioinformatics tools for DNA and protein alignment — descendants of the Needleman–Wunsch and Smith–Waterman algorithms — generalize the exact same prefix-pair recurrence, adding weighted scoring for matches, mismatches, and gaps. Spell-checkers and plagiarism-detection systems use LCS or its close relatives to measure similarity between strings that may differ by small insertions or deletions. Compilers and structural-diff tools for abstract syntax trees use tree-generalized versions of the same idea to produce minimal, human-readable change summaries. The recurrence taught here is also the direct conceptual ancestor of Edit Distance: instead of only "match" or "skip" transitions, edit distance additionally charges a cost for insertion, deletion, and substitution, turning the same $(i,j)$-prefix grid into a minimization instead of a maximization. Anyone comfortable with the LCS table has already done nearly all the conceptual work required for edit distance, and more broadly for the family of sequence-alignment dynamic programs used throughout computational biology and natural language processing.

:::quiz[In the LCS recurrence, what happens when X[i] equals Y[j]?]

• c[i][j] = max(c[i-1][j], c[i][j-1])
• c[i][j] = c[i-1][j-1] + 1 ✓
• c[i][j] = 0
• c[i][j] = c[i][j-1] - 1

Ask the tutor: How does the LCS recurrence change if we also want to allow character substitutions with a cost, turning this into the Edit Distance problem?