Edit Distance

Given two strings $X = x_1 x_2 \dots x_m$ and $Y = y_1 y_2 \dots y_n$, the edit distance $\mathrm{ed}(X, Y)$ is the minimum number of elementary operations needed to transform $X$ into $Y$, where each operation is one of:

• Insertion: add a character to $X$.
• Deletion: remove a character from $X$.
• Substitution: replace one character of $X$ with another character.

This is often called the Levenshtein distance, after Vladimir Levenshtein, who introduced it in the context of error-correcting codes for binary strings. A sequence of operations transforming $X$ into $Y$ is called an edit script, and an optimal edit script is one that achieves $\mathrm{ed}(X, Y)$. The key structural fact is optimal substructure: if you look at the last operation in an optimal edit script that transforms $x_1 \dots x_i$ into $y_1 \dots y_j$, it must be one of a small number of possibilities, and whichever one it is, the rest of the script must itself be an optimal transformation of a strictly smaller pair of prefixes. This is exactly the same flavor of argument used for Longest Common Subsequence, where the last characters of the two sequences either match (extend both) or one of them is dropped. Edit distance simply adds a fourth option — substitution — because unlike LCS, edit distance is allowed to actively change a character rather than only skip it. Formally, define $D[i][j] = \mathrm{ed}(x_1 \dots x_i,\ y_1 \dots y_j)$ for $0 \le i \le m$, $0 \le j \le n$. The base cases are immediate: turning an empty string into $y_1 \dots y_j$ takes $j$ insertions, and turning $x_1 \dots x_i$ into the empty string takes $i$ deletions. The general recurrence, justified in detail below, is

The three terms in the minimum correspond, respectively, to deleting $x_i$, inserting $y_j$, and substituting $x_i$ for $y_j$.

We fill the $(m+1) \times (n+1)$ table $D$ row by row (or column by column — the dependency structure allows either), since each cell depends only on the cell directly above, directly to the left, and diagonally above-left. This is the Memoization versus Tabulation choice made concrete: tabulation here is natural because the subproblem graph is a simple grid with no irregular recursion, so we can iterate in a fixed order instead of recursing with a cache. ``` function EDIT-DISTANCE(X[1..m], Y[1..n]): let D[0..m][0..n] be a new table for i from 0 to m: D[i][0] = i # delete all of X's first i chars for j from 0 to n: D[0][j] = j # insert all of Y's first j chars for i from 1 to m: for j from 1 to n: if X[i] == Y[j]: D[i][j] = D[i-1][j-1] # free match else: deleteCost = D[i-1][j] + 1 # delete X[i] insertCost = D[i][j-1] + 1 # insert Y[j] substituteCost = D[i-1][j-1] + 1 # replace X[i] with Y[j] D[i][j] = min(deleteCost, insertCost, substituteCost) return D[m][n] ``` To recover an actual optimal edit script (not just its length), record which case was chosen at each cell — a standard traceback — and walk from $D[m][n]$ back to $D[0][0]$, emitting the corresponding operation at each step and moving to the predecessor cell. ``` function TRACEBACK(X, Y, D): i, j = m, n script = empty list while i > 0 or j > 0: if i > 0 and j > 0 and X[i] == Y[j] and D[i][j] == D[i-1][j-1]: script.prepend("match " + X[i]) i, j = i-1, j-1 else if i > 0 and j > 0 and D[i][j] == D[i-1][j-1] + 1: script.prepend("substitute " + X[i] + " -> " + Y[j]) i, j = i-1, j-1 else if i > 0 and D[i][j] == D[i-1][j] + 1: script.prepend("delete " + X[i]) i = i-1 else: script.prepend("insert " + Y[j]) j = j-1 return script ```

Time complexity. The table has $(m+1)(n+1)$ cells, and each cell is computed in $O(1)$ time from at most three already-computed neighbors. Hence the total time is

This bound is tight for the DP approach: every cell must be visited at least once because, in the worst case (no shared structure between $X$ and $Y$), each cell's value genuinely depends on distinguishing information not available from any proper subset of cells. There is no known algorithm that solves general edit distance in strongly subquadratic time; a celebrated result (Backurs–Indyk, 2015) shows that an $O((mn)^{1-\epsilon})$ algorithm for any $\epsilon > 0$ would refute the Strong Exponential Time Hypothesis. So $O(mn)$, while not proven optimal in the strongest sense, is believed to be essentially unimprovable in general.

Space complexity. Storing the full table costs $O(mn)$ space, which is also what the traceback procedure needs to recover an explicit edit script. If you only need the distance (not the script), note that row $i$ of $D$ depends only on row $i-1$: rewrite the algorithm to keep just two rows (or one row updated in place with a temporary), reducing space to $O(\min(m, n))$ by always iterating over the shorter string's dimension as the row. This space-for-script tradeoff is a recurring theme in dynamic programming: the compact recurrence is cheap to evaluate, but reconstructing the witness (here, the actual sequence of edits) generally needs the full table, or a divide-and-conquer trick (Hirschberg's algorithm) to get the script in $O(mn)$ time but only $O(\min(m,n))$ space.

Correctness — proof sketch. We prove $D[i][j] = \mathrm{ed}(x_1\dots x_i,\ y_1 \dots y_j)$ by strong induction on $i + j$. Base cases. If $i = 0$, transforming the empty string into $y_1 \dots y_j$ requires exactly $j$ insertions and no fewer (each insertion adds exactly one character, and we need $j$ more characters than we started with), so $D[0][j] = j$ is correct. Symmetrically $D[i][0] = i$. Inductive step. Assume the recurrence is correct for all pairs of prefix-lengths summing to less than $i+j$. Consider any optimal edit script $S$ transforming $x_1\dots x_i$ into $y_1 \dots y_j$, and examine its last operation:

• If $x_i = y_j$ and $S$'s last operation is a match/no-op on these characters (or more precisely, if there's an optimal script that never touches the final matching characters): then removing that trivial step gives an optimal script transforming $x_1 \dots x_{i-1}$ into $y_1 \dots y_{j-1}$, of cost $D[i-1][j-1]$, so $D[i][j] \le D[i-1][j-1]$. Conversely, any script for the smaller prefixes extends for free when the last characters already agree, so $D[i][j] \le D[i-1][j-1]$ is achievable, and it cannot be less, because any transformation of $x_1\dots x_i$ into $y_1 \dots y_j$ induces a transformation of the length-$(i-1)$ and length-$(j-1)$ prefixes (removing the free match cannot increase cost, by a standard argument bounding subsequence transformations by the whole). Hence equality.

• If the last operation is a deletion of $x_i$: the script first optimally transforms $x_1 \dots x_{i-1}$ into $y_1 \dots y_j$ (cost $D[i-1][j]$ by the inductive hypothesis, since $(i-1)+j < i+j$), then deletes $x_i$, total cost $D[i-1][j] + 1$.

• If the last operation is an insertion of $y_j$: symmetric, the script optimally transforms $x_1\dots x_i$ into $y_1 \dots y_{j-1}$ (cost $D[i][j-1]$), then appends $y_j$, total cost $D[i][j-1]+1$.

• If the last operation substitutes $x_i$ for $y_j$ (valid whenever $x_i \ne y_j$, and never helpful when $x_i = y_j$ since that would waste an operation): the script optimally transforms $x_1 \dots x_{i-1}$ into $y_1 \dots y_{j-1}$ (cost $D[i-1][j-1]$), then substitutes, total cost $D[i-1][j-1] + 1$.

Since every edit script's last operation falls into one of these categories (an edit script is, by definition, a sequence of insert/delete/substitute operations, and the very last one applied must be one of the three), the optimal script achieves exactly

which matches the recurrence (the match case is the $x_i = y_j$ specialization where the $+1$ substitution term is skipped in favor of the free diagonal move). By induction, $D[i][j]$ equals the true edit distance for all $i, j$, and in particular $D[m][n] = \mathrm{ed}(X, Y)$. $\blacksquare$

Relationship to LCS. If insertions and deletions cost 1 but substitutions are forbidden (or cost 2, i.e., "delete then insert"), the recurrence degenerates into exactly the Longest Common Subsequence recurrence in disguise: $\mathrm{ed}(X,Y) = m + n - 2\,\mathrm{LCS}(X,Y)$ in that restricted cost model. Allowing genuine unit-cost substitution is what makes Levenshtein distance strictly more general and often smaller than this LCS-derived bound.

Trace `EDIT-DISTANCE` on the classic pair $X = \texttt{kitten}$ ($m = 6$) and $Y = \texttt{sitting}$ ($n = 7$). The completed table $D[i][j]$ (rows indexed by prefixes of `kitten`, columns by prefixes of `sitting`):

Reading a few cells to confirm the recurrence:

• $D[1][1]$: $x_1 =$ `k`, $y_1 =$ `s`, mismatch. $\min(D[0][1]+1, D[1][0]+1, D[0][0]+1) = \min(2,2,1) = 1$. ✓ matches table.
• $D[2][2]$: $x_2 =$ `i`, $y_2 =$ `i`, match. $D[2][2] = D[1][1] = 1$. ✓
• $D[6][7]$ (bottom-right corner): the final answer, $3$.

So $\mathrm{ed}(\texttt{kitten}, \texttt{sitting}) = 3$, matching the well-known result. Running `TRACEBACK` recovers one optimal script:

Three operations, matching $D[6][7] = 3$, and indeed no shorter script exists — you cannot turn "kitten" into "sitting" in two edits, since the strings differ in at least three positions once you correctly account for the length change contributed by the extra `g`. A second, less symmetric example illustrates why substitution genuinely helps beyond plain LCS-style insert/delete. Take $X = \texttt{abcdef}$ and $Y = \texttt{azced}$. Their LCS is `a`,`c`,`e` or similar (length 3), which under the insert/delete-only cost model would suggest $6 + 5 - 2 \cdot 3 = 5$ edits. But with substitution allowed, the DP finds a 3-edit script: substitute `b`→`z`, substitute `d`→`c` is invalid since positions shift — the actual DP correctly threads through matches at `a`, `c`(after shift), `e`, `d` alignment and lands on a distance of 3, strictly better than the insert/delete-only bound of 5. This gap is exactly why Levenshtein's model, not the pure LCS model, is the right tool when substitutions are cheap real-world edits (typos, point mutations).

Version control systems such as Git and diff tools compute edit-distance-like alignments to show minimal, human-readable changes between file revisions. Spell checkers and search-query "did you mean" features rank candidate corrections by Levenshtein distance from the misspelled input, often within a bounded radius (e.g., distance $\le 2$) to keep suggestions fast and relevant. Bioinformatics tools for DNA, RNA, and protein sequence alignment — including the Needleman-Wunsch and Smith-Waterman algorithms — are direct descendants of this recurrence, with the cost matrix replaced by biologically motivated substitution scores (like BLOSUM or PAM matrices) instead of a flat unit cost. Fuzzy matching in databases, plagiarism detectors, OCR post-processing, and speech-recognition error analysis all use edit distance or its weighted variants as the core similarity metric. Because the exact quadratic-time DP does not scale to comparing millions of long sequences, real systems often combine it with filtering heuristics (k-mer indexing, banded DP restricted to a diagonal band when strings are known to be similar) or fall back to faster approximate algorithms — a design pattern that echoes how exact-match string search eventually motivates specialized linear-time algorithms like Knuth-Morris-Pratt String Matching when the problem is narrowed from "how different are these strings" to "does this exact pattern occur here."

:::quiz[What are the four cases in the edit-distance recurrence when filling cell D[i][j]?]

• Match, insert, delete, and swap-adjacent-characters
• Match (free), delete X[i], insert Y[j], substitute X[i] for Y[j] ✓
• Insert, delete, transpose, and reverse
• Match, insert, delete, and no-op only

Ask the tutor: How would the recurrence and complexity change if insertions, deletions, and substitutions each had different, arbitrary costs instead of all costing 1?