Edit Distance

Edit distance works by breaking a string transformation into a decision at the last characters of two prefixes: either they already match (no cost, recurse on both shorter prefixes), or you pay one operation and pick the cheapest of insert, delete, or replace on the shorter sub-problem — the same choice recurs at every prefix pair, so the answer is built bottom-up from tiny prefixes to the full strings.

Recognize the pattern

• Two strings (or sequences) being compared/transformed, and the question asks for a minimum count of operations, or a similarity/alignment score.
• Allowed moves act on a single position at a time (insert/delete/replace, or match/skip) — this signals a 2D grid dp[i][j] over prefixes s1[0..i) and s2[0..j).
• Related siblings: Longest Common Subsequence, DNA sequence alignment, spell-checkers, diff tools — all share the "prefix pair, three neighbor cells" recurrence.

Brute force → optimal

Brute force (recursion): at index (i, j), if characters match, recurse on (i-1, j-1); else try all three ops and take 1 + min of the three recursive calls. Without memoization this branches up to 3-way at every mismatch, giving O(3^(m+n)) time — the same (i, j) pair gets recomputed exponentially many times because multiple operation paths converge on it.

Optimal (DP): notice there are only (m+1)×(n+1) distinct (i, j) states. Cache each state once — either top-down memoization or a bottom-up table — and every state does O(1) work (look at 3 neighbors). That collapses the exponential tree into O(m·n) time.

Complexity, derived

Let m = |s1|, n = |s2|. The state space is every pair (i, j) with 0 ≤ i ≤ m, 0 ≤ j ≤ n: exactly (m+1)(n+1) cells. Each cell does a constant amount of work — one character comparison and a min over 3 already-computed neighbors (up, left, diagonal). Total work = states × work/state = O(m·n) time.

Space: the full table stores all (m+1)(n+1) ints → O(m·n). But row i only ever reads row i-1 (and the current row's left neighbor), so you can roll the table down to two 1D arrays of length n+1, or even one array updated in place with a saved corner value → O(min(m,n)) space (orient the shorter string along the rolled dimension).

Worked example: "bat" → "but"

dp[i][j] = edit distance between s1[0..i) and s2[0..j). Base cases: dp[i][0]=i (delete all), dp[0][j]=j (insert all).

Trace the last row: at (t, t) chars match → dp[3][3] = dp[2][2] = 1. At (a, u) chars differ (row 'a', col 'u') → dp = 1 + min(dp[1][1]=0 replace, dp[1][2]=1 delete, dp[2][1]=1 insert) = 1. Final answer dp[3][3] = 1, matching the single replace 'a'→'u'.

Java (bottom-up, O(min(m,n)) space)

public int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    if (m < n) { String t = s1; s1 = s2; s2 = t; int tmp = m; m = n; n = tmp; }
    int[] prev = new int[n + 1];
    for (int j = 0; j <= n; j++) prev[j] = j;
    for (int i = 1; i <= m; i++) {
        int[] cur = new int[n + 1];
        cur[0] = i;
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                cur[j] = prev[j - 1];
            } else {
                cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
            }
        }
        prev = cur;
    }
    return prev[n];
}

Pitfalls

• Off-by-one on base rows/columns: dp[i][0] and dp[0][j] must be i and j respectively (cost of pure inserts/deletes), not 0 — a common source of wrong answers on empty-string edges.
• Confusing this with LCS: LCS only allows skip on mismatch (no replace), so its recurrence takes max of two neighbors, not 1 + min of three.
• Rolling the array in place without saving the diagonal (prev[j-1]) before overwriting — you'll read an already-updated value and silently corrupt results.

When to use / when not, trade-offs

Use DP edit distance when you need the exact minimum operation count and both strings are modest length (m·n must be tractable — 500×500 = 250k cells is fine, but 10^5×10^5 is not). For very long strings or when you only need a yes/no "similar enough" check, consider bounded edit distance (Ukkonen's algorithm) which runs in O(m·k) where k is the max allowed distance — far cheaper when k is small. If insertions/deletions matter but substitutions don't, LCS-based distance is simpler and cheaper conceptually. For fuzzy matching at scale (e.g., autocomplete over millions of strings), a BK-tree or trie-based approach amortizes the cost across many queries better than recomputing full DP per pair. And if the two strings share the same length and only substitutions are permitted (no insert or delete), edit distance collapses to Hamming distance — a single O(n) count of mismatched positions, no DP needed.

Takeaways

• The recurrence is: match → diagonal free; mismatch → 1 + min(diagonal, up, left).
• O(m·n) time is forced by the number of distinct prefix-pair states; O(min(m,n)) space is achievable because each row only needs the row above.
• Distinguish from LCS (no replace op, max instead of min) before applying this template.

Recall: Why does rolling the DP table down to one 1D array require saving the diagonal value separately before overwriting it?

Pattern: Dynamic Programming — 2D grid over string prefixes; classic reference: Wagner–Fischer algorithm (1974).