Edit Distance

The minimum number of single-character operations (insert, delete, replace) transforming one string into another. Also called Levenshtein distance.

The recurrence

$$dp[i][j]=\{\begin{array}{ll}j& i=0\\ i& j=0\\ dp[i-1][j-1]& a_i=b_j\\ 1+\min (dp[i-1][j],dp[i][j-1],dp[i-1][j-1])& \text{otherwise}\end{array}$$

The three branches are delete from $a$, insert into $a$, and replace.

int editDistance(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<int> prev(m + 1), cur(m + 1);
    for (int j = 0; j <= m; j++) prev[j] = j;
    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++)
            cur[j] = (a[i-1] == b[j-1]) ? prev[j-1]
                   : 1 + min({prev[j], cur[j-1], prev[j-1]});
        swap(prev, cur);
    }
    return prev[m];
}

$O(nm)$ time, $O(\min (n,m))$ space.

The variants

Variant	Allowed operations	Note
Levenshtein	insert, delete, replace	the default
LCS distance	insert, delete only	$=n+m-2\cdot \mathrm{LCS}$
Hamming	replace only	requires equal lengths
Damerau-Levenshtein	+ transpose adjacent	add a fourth branch reading dp[i-2][j-2]
Weighted	different costs per operation	replace the 1 + with the cost
Alphabet-dependent costs	cost depends on the characters	cost[a[i]][b[j]]
Affine gaps	opening a run of gaps costs more than extending	3 layers: match / gap-in-A / gap-in-B (Gotoh)
Local alignment	best matching substring pair	Smith-Waterman: clamp at 0, take the global max

Affine gap penalties matter in bioinformatics and occasionally in contests: a run of $k$ deletions costs $\alpha +\beta k$ rather than $k$. Track three DP layers so the algorithm knows whether it is already inside a gap.

Faster than $O(nm)$

Situation	Method	Time
Answer is known $\le k$	band the DP to $|i-j|\le k$	$O(nk)$
Need the alignment, memory-bound	Hirschberg	$O(nm)$ time, $O(\min (n,m))$ space
Small alphabet, raw speed	Myers’ bit-vector algorithm	$O(nm/64)$
Approximate matching in a text	Bitap	$O(nk/64)$
Very similar strings	Ukkonen’s $O(nd)$ where $d$ = distance	$O(nd)$

Like LCS, edit distance has no $O(n^{2-\epsilon })$ algorithm unless SETH fails — so the quadratic bound is not going to be improved in general.

Banding, concretely

When the problem guarantees the answer is at most $k$, only the diagonal band $|i-j|\le k$ can matter (each step off the diagonal costs at least 1):

for (int i = 1; i <= n; i++)
    for (int j = max(1, i - k); j <= min(m, i + k); j++)
        /* same recurrence, treating out-of-band cells as INF */;

$O(nk)$ — the difference between $10^{10}$ and $10^7$ when $n=10^5$ and $k=100$.

Reconstructing the operations

Walk backwards from dp[n][m], at each step identifying which branch achieved the value:

while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && a[i-1] == b[j-1] && dp[i][j] == dp[i-1][j-1]) { i--; j--; }
    else if (i > 0 && j > 0 && dp[i][j] == dp[i-1][j-1] + 1) { ops.push_back("replace"); i--; j--; }
    else if (i > 0 && dp[i][j] == dp[i-1][j] + 1) { ops.push_back("delete"); i--; }
    else { ops.push_back("insert"); j--; }
}

Check the branches in a fixed order so the output is deterministic — many problems accept any optimal sequence, but some checkers are picky.

Applications

Spell checking, DNA sequence alignment, diff and version control, OCR post-correction, fuzzy search, plagiarism detection, and speech recognition scoring.

See also: LCS · Hirschberg · Bitap