Dynamic programming: LCS and edit distance

What this chapter covers

How different are two strings? How similar are two files? Those questions — behind spell-checkers, diff, autocorrect, fuzzy search, and DNA alignment — are answered by dynamic programming on two sequences at once. Edit distance (Levenshtein distance) counts the fewest single-character edits — insert, delete, substitute — to turn one string into another; kitten becomes sitting in three edits. Longest common subsequence finds the longest run of characters (in order, gaps allowed) shared by both strings; it's how diff lines up two versions of a file. Both are DP over a two-dimensional table indexed by how much of each string you've consumed, where every cell compares one character from each and combines its neighbors' answers. Unlike knapsack's pseudo-polynomial table, this one is genuinely polynomial — O(m·n) — and the naive recursion it replaces is exponential. This chapter builds both, fills the classic Levenshtein grid on screen, and shows the 250-fold blowup the DP avoids.

A bit of history

The two algorithms come from different fields converging on the same DP. Vladimir Levenshtein defined edit distance in 1965 in the context of error-correcting codes — measuring how many character errors a transmitted word could sustain. Independently, biologists needed to align DNA and protein sequences to measure evolutionary similarity, and Saul Needleman and Christian Wunsch published essentially the same dynamic program in 1970 for global sequence alignment, followed by Temple Smith and Michael Waterman's 1981 local-alignment variant — both foundational to bioinformatics, and both edit distance with domain-specific scoring. Longest common subsequence became the basis of file differencing: the Unix diff utility (1976, Doug McIlroy and colleagues) and every version-control system since compute an LCS of two files' lines to show what changed. That three fields — coding theory, computational biology, and systems programming — arrived at the same two-dimensional table is a testament to how fundamental "how similar are these two sequences?" is, and how naturally it yields to dynamic programming.

The intuition

Think about turning A into B one character at a time, working from the ends. Look at the last character of each. If they're the same, they cost nothing — align them and recurse on the rest. If they differ, you have three moves, and you take the cheapest: delete A's last character (and recurse on the rest of A against all of B), insert B's last character (recurse on all of A against the rest of B), or substitute A's last for B's (recurse on the rest of both). Each move costs one edit. That recurrence is correct but exponential, because the same subproblems — "distance between this prefix of A and that prefix of B" — recur across the branches, exactly the overlapping-subproblems situation of the last two chapters.

Dynamic programming lays those subproblems out in a grid. Let dp[i][j] be the edit distance between the first i characters of A and the first j of B. The first row and column are easy: turning an empty string into a j-character prefix takes j inserts, so dp[0][j] = j, and symmetrically dp[i][0] = i. Every other cell is the minimum of three neighbors: dp[i-1][j] + 1 (delete, coming from above), dp[i][j-1] + 1 (insert, from the left), and dp[i-1][j-1] + cost (match or substitute, from the diagonal, where cost is 0 if the characters are equal and 1 if not). Fill the grid row by row and the bottom-right cell is the answer. Longest common subsequence is the same grid with a different rule: when the characters match, dp[i][j] = dp[i-1][j-1] + 1 (extend the diagonal); when they don't, dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (drop one character from whichever side helps). In both, the grid computes each of the m·n subproblems exactly once, and tracing the choices backward from the corner recovers the actual edit script or the actual subsequence.

Complexity: how it scales

The DP is O(m·n) time and space — one pass over the m×n grid, O(1) per cell. (Space can drop to O(min(m,n)) with the rolling-array trick, keeping only the current and previous rows, if you don't need to reconstruct the alignment.) The naive recursion, by contrast, is exponential — roughly O(3^min(m,n)), branching three ways at every mismatch and re-solving shared subproblems. The face-off counts the work directly: naive recursive calls against the DP's grid cells, as the strings grow:

On a log scale the naive line climbs steeply — exponential — while the DP line is nearly flat, growing as the product of the lengths. At length 12 (with a two-letter alphabet, which maximizes the branching), the naive recursion made about 42,000 calls; the DP fills 169 cells — 250 times less work, and the gap explodes with length (at length 20 the naive version would make hundreds of millions of calls; the DP fills 441 cells). This is dynamic programming's signature move once more: an exponential algorithm turned polynomial purely by computing each subproblem once. The difference between "compare two 12-character strings instantly" and "hang on two 30-character strings" is exactly the memory the grid provides.

What it's good at, what it isn't

Sequence DP is the right tool whenever you need to compare, align, or measure the similarity of two ordered sequences. Spell-checkers and autocorrect rank candidate corrections by edit distance to the mistyped word. Fuzzy search and record linkage match approximately-equal strings. diff, git, and every merge tool compute LCS of lines to show and reconcile changes. Bioinformatics aligns DNA, RNA, and protein sequences with weighted variants (Needleman-Wunsch for global, Smith-Waterman for local alignment) to find evolutionary relationships and functional regions. Plagiarism detection, OCR post-correction, speech recognition scoring, and version diffing of any structured data all use it. It also generalizes cleanly — different edit costs, affine gap penalties, and multi-sequence alignment are all elaborations of the same grid.

Where it strains is scale. O(m·n) is fine for words and short sequences but expensive for very long ones — two million-character genomes give a 10¹² cell grid, infeasible directly, which is why bioinformatics uses banded DP (only compute cells near the diagonal), seed-and-extend heuristics (BLAST), or linear-space divide-and-conquer (Hirschberg's algorithm, which computes the alignment in O(m·n) time but O(min) space). For massive-scale or approximate comparison, specialized indexes and hashing (like the MinHash and locality-sensitive hashing used in near-duplicate detection) replace exact DP. And the basic version compares two sequences; aligning many at once (multiple sequence alignment) is NP-hard and needs heuristics. Sequence DP is exact and clean for moderate-length pairs, and the starting point — not the final word — for genome-scale work.

The data, or the inputs

The face-off counts naive recursive calls against the DP's grid-cell count for edit distance, on random two-letter strings (which maximize the branching) of growing length — exponential against polynomial. Correctness is checked thoroughly: on 1500 random string pairs the DP edit distance must equal the naive recursion, the reconstructed edit script must actually transform A into B (and have exactly distance non-match operations), and the LCS length and returned subsequence must match a brute-force LCS and be a genuine common subsequence of both. The animation fills the edit-distance grid for the textbook example kitten → sitting, one row at a time, then traces the alignment path.

Build it, one function at a time

Edit distance — the three-move DP with edit-script reconstruction:

def edit_distance(a, b):
    """Levenshtein distance: fewest insert/delete/substitute edits to turn `a` into `b`. dp[i][j] is
    the distance between the first i characters of a and the first j of b. Deleting a char costs
    dp[i-1][j]+1, inserting costs dp[i][j-1]+1, and matching/substituting costs dp[i-1][j-1] plus 0
    if the characters are equal else 1. Fill the grid and dp[m][n] is the answer. O(m·n). Returns
    (distance, operations) where operations is the reconstructed edit script."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                             # delete all of a's first i chars
    for j in range(n + 1):
        dp[0][j] = j                             # insert all of b's first j chars
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,      # delete a[i-1]
                           dp[i][j - 1] + 1,      # insert b[j-1]
                           dp[i - 1][j - 1] + cost)   # match (cost 0) or substitute (cost 1)
    # backtrace the choices to recover the actual edit script
    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]):
            ops.append(("match" if a[i - 1] == b[j - 1] else "sub", a[i - 1], b[j - 1]))
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(("del", a[i - 1], None))
            i -= 1
        else:
            ops.append(("ins", None, b[j - 1]))
            j -= 1
    return dp[m][n], ops[::-1]

Longest common subsequence — the same grid, match-extends-the-diagonal rule:

def lcs(a, b):
    """Longest common subsequence: the longest string that is a subsequence of both `a` and `b`
    (characters in order, gaps allowed). dp[i][j] is the LCS length of the first i chars of a and
    first j of b: if the characters match, extend the diagonal (dp[i-1][j-1]+1); otherwise take the
    better of dropping a's char (dp[i-1][j]) or b's char (dp[i][j-1]). O(m·n). Returns (length,
    subsequence). This is the engine behind diff."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # walk back to build the subsequence itself
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

Watch it work

Here's the edit-distance grid for kitten → sitting, filled one row at a time. The top row and left column are the base cases — turning an empty string into a prefix takes that many inserts or deletes, so they count up 0, 1, 2, 3… Each interior cell takes the minimum of three neighbors: the cell above plus one (delete), the cell to the left plus one (insert), and the diagonal cell plus zero-if-the-characters-match-else-one. Teal cells mark where the two characters are equal — the "free" diagonal moves. Watch the numbers propagate down and right, each cell one edit away from a cheaper neighbor, until the bottom-right corner reads 3. The orange path traces the alignment backward: substitute k→s, keep itt for free, substitute e→i, keep n, insert g — three edits, and you can read the exact transformation off the diagonal:

The complete code

The from-scratch tab is edit distance (with the reconstructed edit script) and LCS (with the reconstructed subsequence); the library tab is the naive exponential recursion used to verify and to contrast, with a note on Python's difflib for real diffs and similarity. Flip between them — the naive recursion is shorter and obviously correct, and it's exponential; the DP is the same recurrence with the grid as its memory.

"""Edit distance and longest common subsequence — dynamic programming on two sequences at once,
and two of the most useful algorithms in computing. Edit distance (Levenshtein distance) counts the
fewest single-character edits — insert, delete, or substitute — to turn one string into another; it's
what spell-checkers, autocorrect, fuzzy search, and DNA alignment run on. Longest common subsequence
finds the longest sequence of characters appearing in both strings in order (not necessarily
contiguous); it's what `diff` and version control use to line up files.

Both are DP over a two-dimensional state: a table indexed by (how much of string A, how much of
string B) we've consumed. Each cell compares one character of each string and combines the answers
of neighboring cells — diagonal (both consumed), up (one consumed), left (the other). Unlike
knapsack's pseudo-polynomial table, this one is genuinely polynomial: O(m·n) in the two lengths.
The naive recursion, exploring every alignment, is exponential — the same overlapping-subproblems
blowup dynamic programming exists to prevent.
"""


# region: edit_distance
def edit_distance(a, b):
    """Levenshtein distance: fewest insert/delete/substitute edits to turn `a` into `b`. dp[i][j] is
    the distance between the first i characters of a and the first j of b. Deleting a char costs
    dp[i-1][j]+1, inserting costs dp[i][j-1]+1, and matching/substituting costs dp[i-1][j-1] plus 0
    if the characters are equal else 1. Fill the grid and dp[m][n] is the answer. O(m·n). Returns
    (distance, operations) where operations is the reconstructed edit script."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                             # delete all of a's first i chars
    for j in range(n + 1):
        dp[0][j] = j                             # insert all of b's first j chars
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,      # delete a[i-1]
                           dp[i][j - 1] + 1,      # insert b[j-1]
                           dp[i - 1][j - 1] + cost)   # match (cost 0) or substitute (cost 1)
    # backtrace the choices to recover the actual edit script
    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]):
            ops.append(("match" if a[i - 1] == b[j - 1] else "sub", a[i - 1], b[j - 1]))
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(("del", a[i - 1], None))
            i -= 1
        else:
            ops.append(("ins", None, b[j - 1]))
            j -= 1
    return dp[m][n], ops[::-1]
# endregion


# region: lcs
def lcs(a, b):
    """Longest common subsequence: the longest string that is a subsequence of both `a` and `b`
    (characters in order, gaps allowed). dp[i][j] is the LCS length of the first i chars of a and
    first j of b: if the characters match, extend the diagonal (dp[i-1][j-1]+1); otherwise take the
    better of dropping a's char (dp[i-1][j]) or b's char (dp[i][j-1]). O(m·n). Returns (length,
    subsequence). This is the engine behind diff."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # walk back to build the subsequence itself
    out, i, j = [], m, n
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            out.append(a[i - 1])
            i, j = i - 1, j - 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))
# endregion


# region: edit_table
def edit_table(a, b):
    """The full edit-distance table plus, for each cell, which neighbor it came from — used to
    animate the fill and highlight the diagonal alignment path. Move codes: 'diag' (match/sub),
    'up' (delete), 'left' (insert)."""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
    return dp
# endregion

"""The contrast and the library reference. Two things:

- `naive_edit` is the exponential recursion — the same recurrence as the DP but with no memory, so
  it re-solves overlapping subproblems and blows up. It's the correctness cross-check on small
  strings and the 'why DP' contrast in the face-off.
- Python's `difflib` is the standard-library tool that USES these ideas: SequenceMatcher computes
  matching blocks (closely related to LCS) for diffs and similarity ratios. It's what powers
  `difflib.unified_diff`, `get_close_matches`, and the '?' hints in doctest failures.

    import difflib
    difflib.SequenceMatcher(None, a, b).ratio()          # a similarity score in [0,1]
    list(difflib.unified_diff(lines_a, lines_b))         # a line-by-line diff

difflib's algorithm isn't textbook LCS (it favors longer contiguous matches), so it's used here for
illustration, not as an exact LCS oracle — that's what the brute-force check in the trace generator is.
"""


# region: naive
def naive_edit(a, b, calls=None):
    """The direct recursion for edit distance: compare the last characters, and if they differ, try
    all three edits and take the best. No memoization → the same (i, j) subproblems are recomputed
    exponentially many times. `calls` counts invocations to expose the blowup."""
    if calls is not None:
        calls[0] += 1
    if not a:
        return len(b)
    if not b:
        return len(a)
    if a[-1] == b[-1]:
        return naive_edit(a[:-1], b[:-1], calls)
    return 1 + min(
        naive_edit(a[:-1], b, calls),            # delete
        naive_edit(a, b[:-1], calls),            # insert
        naive_edit(a[:-1], b[:-1], calls),       # substitute
    )
# endregion

Scratch vs library

Edit distance and LCS crystallize the two-dimensional DP pattern, and the animation's grid is the mental model worth keeping: sequence-alignment problems are paths through a grid, where you're choosing the cheapest route from corner to corner, and the moves (diagonal, down, right) are the edits. That picture generalizes to every variant — weighted edits, gap penalties, local alignment — as different costs on the same grid, which is why one diagram serves coding theory, biology, and file diffing alike. The chapter also completes the dynamic-programming arc: fundamentals showed the one-dimensional table (coin change), knapsack showed a two-dimensional table with a pseudo-polynomial catch, and this shows a genuinely-polynomial two-dimensional table over two sequences. In production you'd use difflib for diffs, a spell-check library for corrections, or BLAST for genomes; building the grid yourself is what makes diff's output, autocorrect's suggestions, and a sequence alignment legible as the same cheapest-path-through-a-grid computation.

Where you'll actually meet it

Sequence DP runs constantly, often invisibly. Every spell-checker and autocorrect ranks suggestions by edit distance. git, diff, and code-review tools compute LCS of lines to show what changed and to merge branches. Search engines and databases do fuzzy matching and typo tolerance with edit distance. Bioinformatics aligns DNA and proteins with weighted edit distance (Needleman-Wunsch, Smith-Waterman) as the foundation of genomics — BLAST, the most-used tool in biology, is seeded sequence alignment. OCR and speech-recognition systems score outputs against references with it (word error rate is edit distance). Record linkage and data deduplication match near-identical entries. Plagiarism detectors and near-duplicate web-page detection use LCS-like measures. And diff-style comparison of any structured data — configuration, ASTs, documents — reduces to these grids. Wherever "how similar are these two sequences?" is asked, this DP is answering.

Takeaways

Edit distance and longest common subsequence compare two sequences with a two-dimensional DP grid dp[i][j] over prefixes of each string, where every cell combines three neighbors — diagonal (match/substitute), up (delete), left (insert) — in O(1), for O(m·n) total, and backtracking recovers the alignment itself. They're the same grid with the substitution move on (edit distance) or off (LCS, tied to edit distance by m + n − 2·LCS). The DP turns the exponential naive alignment recursion polynomial — 250× less work at length 12 — and it's the engine behind spell-check, diff, and DNA alignment. Sequence problems are cheapest-paths through a grid.

That closes the core dynamic-programming trilogy. The next chapter turns to a different paradigm for the problems where you must search through possibilities rather than fill a table: backtracking. N-Queens, Sudoku, and generating all subsets and permutations are solved by building a candidate incrementally and abandoning it — "pruning" — the moment it can't lead to a solution, a disciplined, depth-first exploration of the space of choices that recovers the exponential brute force only where the problem genuinely demands it.