Sequence Alignment & LCS

How similar are two strings? algorithm and altruistic share the letters a, l, t, i, c in order, and that shared spine, 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.¹ This lesson develops the LCS dynamic program in full, then shows that edit distance is the very same machine 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.

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, 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, the one worth internalizing because it 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.

The answer we want is $\mathrm{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]$.² Write the recurrence as a single $\max$ over three cases, plus a base case:

Read the three branches as moves on the prefixes:

• Case 1 drops $A[i]$: an LCS of $A[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j]$ is a common subsequence of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$, so $\mathrm{OPT}(i,j)\ge \mathrm{OPT}(i-1,j)$.
• Case 2 drops $B[j]$ symmetrically, so $\mathrm{OPT}(i,j)\ge \mathrm{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 $\mathrm{OPT}(i,j)\ge \mathrm{OPT}(i-1,j-1)+1$.

Why exactly these three? Because every common subsequence of $A[\mathrm{1..}i]$ and $B[\mathrm{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. Note that when $A[i]\ne B[j]$, only cases 1 and 2 apply, and the recurrence collapses to $\max (\mathrm{OPT}(i-1,j),\mathrm{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.

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

We claim $\mathrm{OPT}(i,j)=LCS-length(A[\mathrm{1..}i],B[\mathrm{1..}j])$ for all $i,j$, and prove it by induction on $i+j$. The recurrence is itself a $\max$, so the cleanest proof 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. Trivial.

Inductive step. Fix $i,j>0$ and assume the claim for all $i^{\prime },j^{\prime }$ with $i^{\prime }+j^{\prime }<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[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j-1]$ of length $\mathrm{OPT}(i-1,j-1)$. Appending $c$ yields a common subsequence of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$, so $LCS-length(A[\mathrm{1..}i],B[\mathrm{1..}j])\ge \mathrm{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 \mathrm{OPT}(i-1,j)$ and $\ge \mathrm{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[\mathrm{1..}i]$ and $B[\mathrm{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[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j]$, so $|\sigma |\le \mathrm{OPT}(i-1,j)$ by the IH.
• If $\sigma$ does not use $B[j]$: symmetrically $|\sigma |\le \mathrm{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[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j-1]$; hence $|\sigma |-1\le \mathrm{OPT}(i-1,j-1)$, i.e. $|\sigma |\le \mathrm{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, $LCS-length(A[\mathrm{1..}i],B[\mathrm{1..}j])\le \max \{\dots \}$. Both directions together give equality, completing the induction.

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 $\mathrm{OPT}[\mathrm{0..}m][\mathrm{0..}n]$, zero the border, then sweep:

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

The DP table, filled

Take $A=\text{BDCAB}$ and $B=\text{ABCB}$. We build the $(m+1)\times (n+1)$ table of $\mathrm{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.

The bottom-right entry reads $\mathrm{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 $\mathrm{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).

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

Running time and space

The table has $(m+1)(n+1)$ entries, and each is computed in $\Theta (1)$: a comparison and a $\max$. Therefore LCS runs in

time, with $\Theta (mn)$ space for the full table. If only the length is wanted, note that each row depends only on the row above it, so two rows, giving $\Theta (\min (m,n))$ space, suffice. The catch, common to all such DPs: this space trick discards the information needed to reconstruct the subsequence. (Hirschberg's divide-and-conquer refinement recovers the actual LCS in $\Theta (mn)$ time and only linear space, but that is a topic for later.)

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$?³ It is the cost model behind spell-checkers and diff, and it is structurally identical to LCS.

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:

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.

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

Reading the corner, $D(3,4)=2$: align the shared prefix CA for free, substitute T $\to$ R, then insert S. The match cells on the diagonal ($\text{C}$ and $\text{A}$) copy the upper-left value unchanged, exactly the LCS diagonal step but counting saved edits instead of matched characters.

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) falls to the same code.

Takeaways

• Index sequence subproblems by prefixes: $\mathrm{OPT}(i,j)=LCS-length(A[\mathrm{1..}i],B[\mathrm{1..}j])$ is the key that unlocks 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 $\mathrm{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.