---
title: Sequence Alignment & LCS
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 2
order: 802
summary: |
  Two strings can be compared by how much of one appears inside the
  other. The longest common subsequence (LCS) and edit distance are the two
  classic measures, and they are the _same_ dynamic program with different
  costs. We derive the LCS recurrence by examining the last characters, fill a
  worked DP table, reconstruct the subsequence, and then show edit distance as
  the identical $\Theta(mn)$ pattern.
topics: [Dynamic Programming, String Structures]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming"
  - book: Skiena
    ref: "§10 — Dynamic Programming"
  - book: Erickson
    ref: "Ch. 3 — Dynamic Programming"
practice:
  - title: 'Longest Common Subsequence'
    slug: longest-common-subsequence
    difficulty: Medium
  - title: 'Longest Increasing Subsequence'
    slug: longest-increasing-subsequence
    difficulty: Medium
  - title: 'Edit Distance'
    slug: edit-distance
    difficulty: Medium
  - title: 'Longest Palindromic Subsequence'
    slug: longest-palindromic-subsequence
    difficulty: Medium
  - title: 'Distinct Subsequences'
    slug: distinct-subsequences
    difficulty: Hard
---

How similar are two strings? `algorithm` and `altruistic` share the letters
`a`, `l`, `t`, `i`, `c` in order, and that shared string, the **longest common
subsequence**, is one of the most useful measures of similarity in computing. It
underlies the `diff` utility, version-control merges, and (with a change of cost
function) the alignment of DNA and protein sequences in computational biology.[^skiena-lcs]
This lesson develops the LCS dynamic program in full, then shows that **edit
distance** is the same dynamic program with the costs rearranged.

## The problem

A **subsequence** of a string is what remains after deleting zero or more
characters, _keeping the rest in their original order_. It need not be
contiguous: `ace` is a subsequence of `abcde`, but `aec` is not. Given two
strings $X = x_1 x_2 \cdots x_m$ and $Y = y_1 y_2 \cdots y_n$, a **common
subsequence** is a string that is a subsequence of both, and we want a **longest**
one.

A common subsequence is a set of order-preserving matches threading the two
strings: the matched letters appear in both, left to right, though the gaps
between them differ.

$$
% caption: A common subsequence threads order-preserving matches through both strings.
%          Here $ALRIT$ is the longest common subsequence of $ALGORITHM$ and $ALTRUISTIC$;
%          matched letters connect, the rest are skipped.
\begin{tikzpicture}[
  >=Stealth,
  lt/.style={font=\small, inner sep=1.5pt, minimum size=5mm},
  sk/.style={lt, black},
  mt/.style={lt, acc},
  link/.style={draw=acc, thick}]
  \definecolor{acc}{HTML}{2348F2}
  % top string ALGORITHM (index k at x = 0.6k); matched: 0,1,4,5,6
  \foreach \ch/\k/\s in {A/0/mt,L/1/mt,G/2/sk,O/3/sk,R/4/mt,I/5/mt,T/6/mt,H/7/sk,M/8/sk}
    \node[\s] (t-\k) at (0.6*\k,0.9) {\ch};
  % bottom string ALTRUISTIC; matched: 0,1,3,5,7
  \foreach \ch/\k/\s in {A/0/mt,L/1/mt,T/2/sk,R/3/mt,U/4/sk,I/5/mt,S/6/sk,T/7/mt,I/8/sk,C/9/sk}
    \node[\s] (b-\k) at (0.6*\k,-0.9) {\ch};
  % matches A(t0,b0) L(t1,b1) R(t4,b3) I(t5,b5) T(t6,b7)
  \draw[link] (t-0) -- (b-0);
  \draw[link] (t-1) -- (b-1);
  \draw[link] (t-4) -- (b-3);
  \draw[link] (t-5) -- (b-5);
  \draw[link] (t-6) -- (b-7);
  \node[font=\footnotesize, acc] at (6.7,0) {LCS $=$ ALRIT};
\end{tikzpicture}
$$

> **Input:** strings $X[1..m]$ and $Y[1..n]$.
> **Output:** a longest string that is a subsequence of both $X$ and $Y$.

A brute-force search is hopeless: $X$ has $2^m$ subsequences, and checking each
against $Y$ gives $\Theta(n\,2^m)$. We need the [recipe](/algorithms/dynamic-programming/principles),
and it pays to follow it literally. The DP recipe runs through fixed steps: **(0)** simplify the
goal, **(1)** define the subproblems and notation, **(2)** write the DP equations,
**(3)** prove them correct by induction, **(4)** turn them into iterative
pseudocode, **(5)** return to the original goal, then analyze. We walk LCS through
those steps verbatim.

## Step 0–1: Simplify the goal, define the subproblem

**Simplify first.** Computing the _string_ drags around bookkeeping; computing its
**length** is cleaner. So we first solve for the LCS _length_, then recover an
actual subsequence in a cheap second pass (Step 5). With that simplification, the
decisive move, which recurs across all
sequence DPs, is to index subproblems by **prefixes** of the two strings. Write
$A = X$ and $B = Y$ for the two inputs.

> **Definition (LCS subproblem).** Let $\OPT(i, j) = \operatorname{LCS-length}\parens{A[1..i],\,B[1..j]}$,
> the length of a longest common subsequence of the prefixes $A[1..i]$ and
> $B[1..j]$.

The answer we want is $\OPT(m, n)$. There are $(m+1)(n+1)$
subproblems, one per pair of prefix lengths $0 \le i \le m$ and $0 \le j \le n$.

## Step 2: The DP equations

Now apply optimal substructure by looking at the **last** characters, $A[i]$ and
$B[j]$.[^clrs-lcs] Write the recurrence as a single $\max$ over three cases,
plus a base case:

$$
\OPT(i,j) =
\begin{cases}
0 & \text{if } i = 0 \text{ or } j = 0, \quad\text{(case 0)} \\[6pt]
\max\begin{cases}
  \OPT(i-1, j) & \text{(case 1)} \\
  \OPT(i, j-1) & \text{(case 2)} \\
  \OPT(i-1, j-1) + 1 & \text{if } A[i] = B[j] \quad\text{(case 3)}
\end{cases} & \text{if } i, j > 0.
\end{cases}
$$

Read the three branches as moves on the prefixes:

- **Case 1** drops $A[i]$: an LCS of $A[1..i-1]$ and $B[1..j]$ is a common
  subsequence of $A[1..i]$ and $B[1..j]$, so $\OPT(i,j) \ge \OPT(i-1,j)$.
- **Case 2** drops $B[j]$ symmetrically, so $\OPT(i,j) \ge \OPT(i,j-1)$.
- **Case 3** fires _only when_ $A[i] = B[j]$: the shared character $c = A[i] = B[j]$
  can end an optimal LCS, so we append it to the best LCS of the strictly shorter
  prefixes, giving $\OPT(i,j) \ge \OPT(i-1, j-1) + 1$.

Why exactly these three? Because every common subsequence of $A[1..i]$ and
$B[1..j]$ falls into one of three shapes: it ignores $A[i]$ (case 1), ignores
$B[j]$ (case 2), or uses both as a final match (case 3, possible only if
$A[i]=B[j]$). The $\max$ over the applicable cases is the longest of them. When
$A[i] \ne B[j]$, only cases 1 and 2 apply, and the recurrence collapses to
$\max\parens{\OPT(i-1,j),\,\OPT(i,j-1)}$.

Each entry depends only on its left, upper, and upper-left neighbors, so filling
the table **row by row, left to right** (or column by column) respects every
dependency. The same three-neighbour stencil drives _every_ sequence DP below:
only the labels on the arrows change.

$$
% caption: The shared stencil of every sequence DP: cell $(i,j)$ reads its left, upper,
%          and upper-left neighbours; the diagonal fires on a match ($A[i]=B[j]$), the
%          other two on a drop or an edit.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=11mm, inner sep=1pt, font=\small},
  cur/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (d) at (0,0) {(i-1, j-1)};
  \node[cell] (u) at (1.8,0) {(i-1, j)};
  \node[cell] (l) at (0,-1.8) {(i, j-1)};
  \node[cur]  (c) at (1.8,-1.8) {(i, j)};
  \draw[->, thick, acc] (d.south east) -- (c.north west);
  \draw[->, thick] (u.south) -- (c.north);
  \draw[->, thick] (l.east) -- (c.west);
  \node[lbl, acc, fill=white, inner sep=1.5pt] at (0.55,-0.75) {match +1 / free};
  \node[lbl] at (2.85,-0.9) {drop / edit};
  \node[lbl] at (0.9,-2.55) {drop / edit};
\end{tikzpicture}
$$

## Step 3: Correctness by induction on $i + j$

> **Claim.** $\OPT(i,j) = \operatorname{LCS-length}(A[1..i], B[1..j])$
> for all $i, j \ge 0$.

> **Proof.** By induction on $i + j$. The recurrence is itself a $\max$, so the
> cleanest argument shows two inequalities: that the recurrence is neither too
> small ($\ge$) nor too large ($\le$).
>
> **Base case** ($i + j = 0$, i.e. $i = 0$ or $j = 0$). One prefix is empty, so the
> only common subsequence is empty and the length is $0$, exactly case 0.
>
> **Inductive step.** Fix $i, j > 0$ and assume the claim for all $i', j'$ with
> $i' + j' < i + j$.
>
> _The $\ge$ direction_ (the recurrence is achievable). We exhibit a common
> subsequence of length at least the right-hand side.
>
> - If $A[i] = B[j] = c$: by the induction hypothesis there is a common subsequence
>   of $A[1..i-1]$ and $B[1..j-1]$ of length $\OPT(i-1, j-1)$.
>   Appending $c$ yields a common subsequence of $A[1..i]$ and $B[1..j]$, so
>   $\operatorname{LCS-length}(A[1..i], B[1..j]) \ge \OPT(i-1, j-1) + 1$.
> - Cases 1 and 2 are even simpler: any common subsequence of a shorter prefix pair
>   is still common for the longer pair, giving $\ge \OPT(i-1, j)$ and
>   $\ge \OPT(i, j-1)$. So the true length is $\ge$ the $\max$.
>
> _The $\le$ direction_ (the recurrence is not exceeded). Take **any** common
> subsequence $\sigma$ of $A[1..i]$ and $B[1..j]$; we show $|\sigma|$ is bounded by
> one of the three branches.
>
> - If $\sigma$ does not use $A[i]$: then $\sigma$ is a common subsequence of
>   $A[1..i-1]$ and $B[1..j]$, so $|\sigma| \le \OPT(i-1, j)$ by the IH.
> - If $\sigma$ does not use $B[j]$: symmetrically $|\sigma| \le \OPT(i, j-1)$.
> - If $\sigma$ uses **both** $A[i]$ and $B[j]$: then they must match as $\sigma$'s
>   last character, so $A[i] = B[j]$, and dropping it leaves a common subsequence of
>   $A[1..i-1]$ and $B[1..j-1]$; hence $|\sigma| - 1 \le \OPT(i-1, j-1)$,
>   i.e. $|\sigma| \le \OPT(i-1, j-1) + 1$.
>
> One of these three cases always applies, so $|\sigma| \le \max\{\dots\}$ over the
> applicable branches. Taking $\sigma$ to be a _longest_ common subsequence,
> $\operatorname{LCS-length}(A[1..i], B[1..j]) \le \max\{\dots\}$. Both directions
> together give equality, completing the induction. $\qed$

## Step 4: Iterative pseudocode

The equations are non-circular, since every entry reads strictly smaller prefixes, so
they convert directly into a bottom-up table fill. Allocate
$\OPT[0..m][0..n]$, zero the border, then sweep:

```algorithm
caption: $\textsc{LCS-Length}(A[1..m], B[1..n])$ — fill the DP table
number: 1
for $i \gets 0$ to $m$ do
  $\OPT[i][0] \gets 0$ // empty $B$ prefix
for $j \gets 0$ to $n$ do
  $\OPT[0][j] \gets 0$ // empty $A$ prefix
for $i \gets 1$ to $m$ do
  for $j \gets 1$ to $n$ do
    $\OPT[i][j] \gets \max\parens{\OPT[i-1][j],\ \OPT[i][j-1]}$ // cases 1, 2
    if $A[i] = B[j]$ then
      $\OPT[i][j] \gets \max\parens{\OPT[i][j],\ \OPT[i-1][j-1] + 1}$ // case 3
return $\OPT[m][n]$
```

Every cell costs $\Theta(1)$, so the fill is $\Theta(mn)$.

## The DP table, filled

Take $A = \texttt{BDCAB}$ and $B = \texttt{ABCB}$. We build the
$(m+1) \times (n+1)$ table of $\OPT(i, j)$ values. Row $0$ and column
$0$ are all zero (empty prefix); every other cell is filled by the recurrence. The
shaded diagonal steps mark the matches that build the answer, and the red arrows
trace the reconstruction walk (Step 5) backwards from the corner.

$$
% caption: Filled LCS table for $BDCAB$ and $ABCB$ with the traceback path arrowed.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  hdr/.style={draw=none, font=\small},
  match/.style={cell, fill=black!12},
  back/.style={-{Stealth[length=2mm]}, red!75!black, thick}]
  % column headers
  \node[hdr] at (1,0) {\texttt{""}};
  \node[hdr] at (2,0) {A};
  \node[hdr] at (3,0) {B};
  \node[hdr] at (4,0) {C};
  \node[hdr] at (5,0) {B};
  % row labels
  \node[hdr] at (0,-1) {\texttt{""}};
  \node[hdr] at (0,-2) {B};
  \node[hdr] at (0,-3) {D};
  \node[hdr] at (0,-4) {C};
  \node[hdr] at (0,-5) {A};
  \node[hdr] at (0,-6) {B};
  % row varnothing
  \node[cell] at (1,-1) {0}; \node[cell] at (2,-1) {0}; \node[cell] at (3,-1) {0}; \node[cell] at (4,-1) {0}; \node[cell] at (5,-1) {0};
  % row B
  \node[cell] at (1,-2) {0}; \node[cell] at (2,-2) {0}; \node[match] at (3,-2) {1}; \node[cell] at (4,-2) {1}; \node[match] at (5,-2) {1};
  % row D
  \node[cell] at (1,-3) {0}; \node[cell] at (2,-3) {0}; \node[cell] at (3,-3) {1}; \node[cell] at (4,-3) {1}; \node[cell] at (5,-3) {1};
  % row C
  \node[cell] at (1,-4) {0}; \node[cell] at (2,-4) {0}; \node[cell] at (3,-4) {1}; \node[match] at (4,-4) {2}; \node[cell] at (5,-4) {2};
  % row A
  \node[cell] at (1,-5) {0}; \node[match] at (2,-5) {1}; \node[cell] at (3,-5) {1}; \node[cell] at (4,-5) {2}; \node[cell] at (5,-5) {2};
  % row B
  \node[cell] at (1,-6) {0}; \node[cell] at (2,-6) {1}; \node[match] at (3,-6) {2}; \node[cell] at (4,-6) {2}; \node[match] at (5,-6) {3};
  % traceback path (5,-6)->(4,-5)->(4,-4)->(3,-3)->(3,-2)->(2,-1); arrows are
  % shortened to sit in the gaps between cells so they never cross the digits.
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (5,-6) -- (4,-5);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (4,-5) -- (4,-4);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (4,-4) -- (3,-3);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (3,-3) -- (3,-2);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (3,-2) -- (2,-1);
\end{tikzpicture}
$$

The bottom-right entry reads $\OPT(5, 4) = 3$: the longest common
subsequence of `BDCAB` and `ABCB` has length $3$, namely `BCB` (the only one here,
though in general there may be ties). The arrows enter each shaded **match** cell
diagonally (emitting `B`, then `C`, then `B`, read from the corner upward) and step
straight up or left through non-match cells, exactly as the reconstruction below
prescribes.

## Step 5: Reconstructing the subsequence

The table gives the _length_; this is where the Step 0 simplification is paid back.
In a **second pass** we walk **backwards** from $\OPT(m, n)$, undoing
the recurrence. At cell $(i, j)$: if $A[i] = B[j]$, that character belongs to the
LCS — emit it and step diagonally to $(i-1, j-1)$ (case 3); otherwise move to
whichever neighbor, up or left, holds the larger value (the one the $\max$ of cases
1 and 2 chose).

```algorithm
caption: $\textsc{LCS-Reconstruct}(A, B, \OPT, i, j)$ — recover the subsequence
number: 2
if $i = 0$ or $j = 0$ then
  return the empty string // empty prefix
if $A[i] = B[j]$ then
  return $\textsc{LCS-Reconstruct}(A, B, \OPT, i-1, j-1)$ followed by $A[i]$ // case 3 match
else if $\OPT[i-1][j] \ge \OPT[i][j-1]$ then
  return $\textsc{LCS-Reconstruct}(A, B, \OPT, i-1, j)$ // from above (case 1)
else
  return $\textsc{LCS-Reconstruct}(A, B, \OPT, i, j-1)$ // from left (case 2)
```

The walk takes one step toward the origin each call, so it runs in $O(m + n)$
time, cheap compared with building the table.

Trace it on the worked table above, starting at $(5, 4)$ with value $3$. The red
arrows in the figure _are_ this walk:

- $(5,4)$: $A[5] = \texttt{B} = B[4]$, a match. Emit `B`, step to $(4, 3)$.
- $(4,3)$: $A[4] = \texttt{A} \ne \texttt{C} = B[3]$. Compare the up neighbour
  $\OPT(3,3) = 1$ against the left neighbour $\OPT(4,2) = 1$;
  the tie breaks upward, step to $(3, 3)$.
- $(3,3)$: $A[3] = \texttt{C} = B[3]$, a match. Emit `C`, step to $(2, 2)$.
- $(2,2)$: $A[2] = \texttt{D} \ne \texttt{A} = B[2]$. Up neighbour $\OPT(1,2) = 1$
  ties left neighbour $\OPT(2,1) = 0$; step up to $(1, 2)$.
- $(1,2)$: $A[1] = \texttt{B} = B[2]$, a match. Emit `B`, step to $(0, 1)$.
- $(0,1)$: $i = 0$, stop.

The emitted characters, corner-first, are `B`, `C`, `B`; reversed into forward order
they read `BCB` — the length-$3$ LCS the corner promised. The tie-break rule (up
before left) is arbitrary; the other choice would recover an equally long
subsequence, and a longest common subsequence need not be unique.

## Running time and space

The table has $(m+1)(n+1)$ entries. Filling one costs a character comparison and a
$\max$ of at most three previously-computed neighbours, all $\Theta(1)$. Summing
over the fill,
$$
\sum_{i=1}^{m}\sum_{j=1}^{n} \Theta(1) = \Theta(mn),
$$
and the border initialization adds only $\Theta(m + n)$, which $\Theta(mn)$
absorbs. The reconstruction pass is $O(m + n)$, also absorbed. LCS therefore runs
in $\Theta(mn)$ time — a decisive improvement over the $\Theta(n\,2^m)$ brute force,
and for two length-$1000$ strings the difference is a million cell updates against
roughly $10^{300}$ subsequence checks.

Space is $\Theta(mn)$ for the full table, but the recurrence reads only the current
row and the one directly above it. Keeping two length-$(n+1)$ rows and swapping them
after each $i$ (a **rolling array**) drops the footprint to $\Theta(n)$, and
choosing the shorter string as the inner axis makes it $\Theta(\min(m, n))$.

$$
% caption: Rolling-array space optimization. Cell $(i,j)$ reads only the previous row
%          (upper and upper-left) and the current row's left neighbour, so two rows
%          suffice; after finishing row $i$ the previous row is discarded and the buffers
%          swap.
\begin{tikzpicture}[
  >=Stealth,
  slot/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  prev/.style={slot, fill=black!10},
  curr/.style={slot, fill=acc!16},
  rlab/.style={draw=none, font=\footnotesize, black}]
  \definecolor{acc}{HTML}{2348F2}
  % previous row (row i-1)
  \foreach \k in {0,...,5} \node[prev] (p\k) at (\k,0.9) {};
  % current row (row i), building left to right
  \foreach \k in {0,...,5} \node[curr] (c\k) at (\k,0) {};
  \node[rlab] at (-1.55,0.9) {row i-1};
  \node[rlab] at (-1.4,0) {row i};
  % the cell being computed is c3; its three sources
  \node[curr, fill=acc!45] (target) at (3,0) {};
  \draw[->, thick, acc] (p3.south) -- (target.north);
  \draw[->, thick, acc] (p2.south east) -- (target.north west);
  \draw[->, thick, acc] (c2.east) -- (target.west);
  \node[draw=none, font=\footnotesize] at (7.5,0.5) {reads: directly above,};
  \node[draw=none, font=\footnotesize] at (7.5,0.05) {above-\/left,};
  \node[draw=none, font=\footnotesize] at (7.5,-0.4) {and left};
\end{tikzpicture}
$$

The catch is universal to this trick: collapsing the table erases the information the
traceback needs, so the two-row version yields only the length, never the
subsequence itself. Recovering the actual alignment in linear space is possible —
Hirschberg's divide-and-conquer refinement does it in $\Theta(mn)$ time and $\Theta(\min(m,n))$
space[^erickson-hirschberg] — but that machinery is a topic for later.

::impl{algo="longest_common_subsequence,longest_palindromic_subsequence,longest_increasing_subsequence,distinct_subsequences"}

## The same machine: edit distance

**Edit distance** (the **Levenshtein distance**) asks the closely related
question: what is the minimum number of single-character **insertions**,
**deletions**, and **substitutions** that transform $A$ into $B$?[^erickson-editdist] It is the cost
model behind spell-checkers and `diff`, and it is _structurally identical_ to LCS.

> **Definition (Edit distance).** Let $D(i, j)$ be the edit distance between the prefixes $A[1..i]$ and $B[1..j]$.

Again we look at the last characters. If $A[i] = B[j]$, they need no edit and we
align them for free. Otherwise we make one of three moves (delete $A[i]$, insert
$B[j]$, or substitute $A[i] \to B[j]$), each at cost $1$, and recurse on the
correspondingly shorter prefixes:
$$
D(i,j) =
\begin{cases}
i & \text{if } j = 0, \\[3pt]
j & \text{if } i = 0, \\[3pt]
D(i-1, j-1) & \text{if } A[i] = B[j], \\[3pt]
1 + \min\!\begin{cases}
  D(i-1, j) & \text{(delete } A[i]) \\
  D(i, j-1) & \text{(insert } B[j]) \\
  D(i-1, j-1) & \text{(substitute)}
\end{cases} & \text{if } A[i] \neq B[j].
\end{cases}
$$
The base cases say it: turning a length-$i$ prefix into the empty string costs $i$
deletions, and building a length-$j$ prefix from nothing costs $j$ insertions.

It is the same three-neighbour stencil as LCS — only the arrow labels change. The
diagonal is free on a match and costs $1$ to substitute; a step down deletes $A[i]$,
a step right inserts $B[j]$, each at cost $1$. We take the cheapest incoming move
instead of the longest:

$$
% caption: Edit distance's three moves into cell $(i,j)$: the diagonal is free on a
%          match and costs $1$ to substitute, a step down deletes $A[i]$, and a step
%          right inserts $B[j]$ — the LCS stencil, now minimizing edits instead of
%          maximizing matches.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=11mm, inner sep=1pt, font=\small},
  cur/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cell] (d) at (0,0) {(i-1, j-1)};
  \node[cell] (u) at (1.8,0) {(i-1, j)};
  \node[cell] (l) at (0,-1.8) {(i, j-1)};
  \node[cur]  (c) at (1.8,-1.8) {(i, j)};
  \draw[->, thick, acc] (d.south east) -- (c.north west);
  \draw[->, thick] (u.south) -- (c.north);
  \draw[->, thick] (l.east) -- (c.west);
  \node[lbl, acc, fill=white, inner sep=1.5pt] at (0.45,-0.82) {match 0 / sub +1};
  \node[lbl] at (2.78,-0.9) {delete +1};
  \node[lbl] at (0.95,-2.55) {insert +1};
\end{tikzpicture}
$$

Filled on a small pair, the table looks just like the LCS one but now
_minimizes_. Take $A = \texttt{CAT}$ and $B = \texttt{CARS}$: the shaded diagonal
marks the free matches, and the corner reports the answer.

$$
% caption: Edit-distance table $D(i,j)$ for $A=\texttt{CAT}\to B=\texttt{CARS}$; the
%          corner $D(3,4)=2$ counts one substitution ($\texttt{T}\to\texttt{R}$) and one
%          insertion ($\texttt{S}$). The red arrows trace the alignment back: a diagonal
%          step is a match or substitution, a horizontal step an insertion.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  hdr/.style={draw=none, font=\small},
  match/.style={cell, fill=black!12},
  ans/.style={cell, fill=acc!18},
  back/.style={-{Stealth[length=2mm]}, red!75!black, thick}]
  \definecolor{acc}{HTML}{2348F2}
  \node[hdr] at (1,0) {\texttt{""}};
  \node[hdr] at (2,0) {C};
  \node[hdr] at (3,0) {A};
  \node[hdr] at (4,0) {R};
  \node[hdr] at (5,0) {S};
  \node[hdr] at (0,-1) {\texttt{""}};
  \node[hdr] at (0,-2) {C};
  \node[hdr] at (0,-3) {A};
  \node[hdr] at (0,-4) {T};
  \node[cell] at (1,-1) {0}; \node[cell] at (2,-1) {1}; \node[cell] at (3,-1) {2}; \node[cell] at (4,-1) {3}; \node[cell] at (5,-1) {4};
  \node[cell] at (1,-2) {1}; \node[match] at (2,-2) {0}; \node[cell] at (3,-2) {1}; \node[cell] at (4,-2) {2}; \node[cell] at (5,-2) {3};
  \node[cell] at (1,-3) {2}; \node[cell] at (2,-3) {1}; \node[match] at (3,-3) {0}; \node[cell] at (4,-3) {1}; \node[cell] at (5,-3) {2};
  \node[cell] at (1,-4) {3}; \node[cell] at (2,-4) {2}; \node[cell] at (3,-4) {1}; \node[cell] at (4,-4) {1}; \node[ans] at (5,-4) {2};
  % traceback (5,-4)->(4,-4) insert -> (3,-3) subst -> (2,-2) match -> (1,-1) match;
  % shortened so each arrow sits in the gap between cells, clear of the digits
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (5,-4) -- (4,-4);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (4,-4) -- (3,-3);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (3,-3) -- (2,-2);
  \draw[back, shorten <=3.2mm, shorten >=3.2mm] (2,-2) -- (1,-1);
\end{tikzpicture}
$$

Reading the corner, $D(3,4) = 2$. The traceback recovers the alignment itself,
walking corner to origin and reading each step as the edit that produced it:

- $(3,4)$ value $2$: the left neighbour $D(3,3) = 1$ is one cheaper, so this step
  is an **insertion** of $B[4] = \texttt{S}$. Move left to $(3, 3)$.
- $(3,3)$ value $1$: $A[3] = \texttt{T} \ne \texttt{R} = B[3]$, and the upper-left
  $D(2,2) = 0$ is the cheapest source, so this is a **substitution**
  `T` $\to$ `R`. Move diagonally to $(2, 2)$.
- $(2,2)$ value $0$: $A[2] = \texttt{A} = B[2]$, a **free match**. Move diagonally
  to $(1, 1)$.
- $(1,1)$ value $0$: $A[1] = \texttt{C} = B[1]$, a **free match**. Move to $(0, 0)$
  and stop.

Read forward, the alignment is: keep `C`, keep `A`, substitute `T` $\to$ `R`, insert
`S` — turning `CAT` into `CARS` in the promised two edits. The match cells on the
diagonal ($\texttt{C}$ and $\texttt{A}$) copy the upper-left value unchanged, the
same LCS diagonal step, but counting saved edits instead of matched characters.

The fill is the LCS loop with $\min$ in place of $\max$ and the borders seeded to
the prefix lengths rather than zeros:

```algorithm
caption: $\textsc{Edit-Distance}(A[1..m], B[1..n])$ — fill the DP table
number: 3
for $i \gets 0$ to $m$ do
  $D[i][0] \gets i$ // delete all of $A[1..i]$
for $j \gets 0$ to $n$ do
  $D[0][j] \gets j$ // insert all of $B[1..j]$
for $i \gets 1$ to $m$ do
  for $j \gets 1$ to $n$ do
    if $A[i] = B[j]$ then
      $D[i][j] \gets D[i-1][j-1]$ // free match
    else
      $D[i][j] \gets 1 + \min\parens{D[i-1][j],\ D[i][j-1],\ D[i-1][j-1]}$ // delete, insert, substitute
return $D[m][n]$
```

Every cell is still $\Theta(1)$, so the fill is $\Theta(mn)$, and the alignment is
recovered by the same corner-to-origin traceback as LCS.

::impl{algo="edit_distance"}

Compare this against LCS line by line. Both index subproblems by prefix pairs;
both branch on whether the last characters match; both fill an
$(m+1)\times(n+1)$ table where each entry reads its left, upper, and upper-left
neighbors; both run in $\Theta(mn)$. The _only_ differences are the costs and
the optimization direction: LCS **maximizes** matched characters, edit distance
**minimizes** edits. **Sequence DPs are a single template**, parameterized by
what a "match" earns and a "mismatch" costs. Recognize the template and a whole
family of problems (LCS, edit distance, sequence alignment, longest common
substring, and [string matching](/algorithms/sequences/string-matching)) falls
to the same code.

## Alignment, bioinformatics, and the quadratic wall

The LCS/edit-distance template is the single most consequential dynamic program in
applied computing, because it _is_ **sequence alignment**. Needleman and Wunsch
(1970) introduced the $\Theta(mn)$ global-alignment DP for comparing protein and
nucleotide sequences; Smith and Waterman (1981) adapted it to _local_ alignment
(the best-matching substring pair, by clamping the score at $0$ and tracking the
global maximum, the same move the [maximum-subarray](/algorithms/sequences/prefix-sums)
DP makes). These two recurrences are the foundation of computational biology, and
the `diff` utility, `git`'s merge machinery, spell checkers, and DNA read-mapping
all descend from the same table. Gotoh (1982) refined the model with **affine gap
penalties** — charging a large cost to _open_ a gap and a small cost to _extend_ it,
which needs three coupled tables but stays $\Theta(mn)$ — because a single long
insertion is biologically more plausible than many scattered ones.

The catch is scale. A $\Theta(mn)$ table is fine for two short strings but ruinous
for two human chromosomes, and the [Hirschberg linear-space
trick](/algorithms/dynamic-programming/principles) (noted above) fixes the memory
but not the time. Whether the _time_ can be beaten is now settled conditionally:
Backurs and Indyk (2015) and Bringmann and Künnemann (2015) proved that edit
distance and LCS admit no strongly subquadratic $O(n^{2-\varepsilon})$ algorithm
unless the Strong Exponential Time Hypothesis is false. So the quadratic table is a
genuine wall, and the practical response has been to give up exactness: heuristic
aligners like **BLAST** (Altschul et al., 1990) and **FASTA** seed on short exact
matches and extend them, trading a guarantee of optimality for the speed that made
genome-scale search possible. The abstract "define the subproblem, fill the table"
discipline of this lesson is, in this one instance, a multi-billion-dollar tool.[^seq-beyond]

## Takeaways

- Index sequence subproblems by **prefixes**:
  $\OPT(i, j) = \operatorname{LCS-length}(A[1..i], B[1..j])$ is the
  key to LCS, after the Step 0 move of solving for _length_ first.
- The recurrence is a $\max$ over three cases (drop $A[i]$ in case 1, drop $B[j]$
  in case 2, or extend the diagonal by $1$ when $A[i] = B[j]$ in case 3) over a base
  case of $0$ for an empty prefix.
- **Prove it by induction on $i+j$ in two directions**: $\ge$ (build a witness
  subsequence) and $\le$ (every common subsequence fits one of the three cases).
- Fill the $(m+1)\times(n+1)$ table in $\Theta(mn)$; **reconstruct** in a second
  pass, walking backwards from $\OPT(m,n)$ and emitting a character on
  every diagonal match.
- Only the length is needed? Two rows give $\Theta(\min(m,n))$ space, at the
  cost of losing the reconstruction.
- **Edit distance is the same dynamic program**: same prefix subproblems, same
  table shape, same $\Theta(mn)$, minimizing edits instead of maximizing
  matches. Sequence DP is one reusable template.

[^skiena-lcs]: **Skiena**, §10 — Dynamic Programming: the longest common subsequence as a similarity measure underlying `diff` and sequence alignment.
[^clrs-lcs]: **CLRS**, Ch. 15 — Dynamic Programming: the LCS recurrence obtained by examining the last characters of each prefix.
[^erickson-editdist]: **Erickson**, Ch. 3 — Dynamic Programming: edit (Levenshtein) distance as the minimum-cost insert/delete/substitute alignment filling an $m\times n$ table.
[^erickson-hirschberg]: **Erickson**, Ch. 3 — Dynamic Programming: Hirschberg's divide-and-conquer computes an optimal alignment in linear space by recursing on the midpoint column, keeping the $\Theta(mn)$ time bound.
[^seq-beyond]: **Needleman & Wunsch** (1970) global and **Smith & Waterman** (1981) local sequence alignment; **Gotoh** (1982) affine gaps. **Backurs & Indyk** (2015) and **Bringmann & Künnemann** (2015): no strongly subquadratic edit distance / LCS under SETH — the practical reason heuristic aligners like **BLAST** (Altschul et al., 1990) exist.