Edit distance

The problem it solves

How far apart are two strings? Not “are they equal” — how many single-character operations (insert, delete, substitute) turn one into the other. That number, the Levenshtein distance, is the engine inside spell-checkers (“did you mean…” is a small-radius edit-distance search), fuzzy matching, DNA mutation measurement, OCR correction, and every system that must judge “close enough”. kitten → sitting is 3: substitute k→s, substitute e→i, insert g — and the algorithm on this page both finds that number and can exhibit the three edits.

Its interview status is peculiar: it’s the hard member of the classic DP set, not because the code is long but because it demands you hold a precise meaning in every cell and a precise meaning on every arrow — and questions probe the arrows.

The intuition — and where it breaks down

Imagine a typist converting one word into another, working left to right, never revisiting finished ground. At each moment, some prefix of the source has been consumed and some prefix of the target has been produced. The typist’s options at any point are exactly three: type a character the source doesn’t have (insert — target grows, source stands still), skip a source character (delete — source shrinks, target stands still), or transform the current source character into the current target character (substitute — both advance; free if they already match).

Now the DP reading: dp[i][j] = fewest operations turning the first i characters of source into the first j of target. The three options are the three neighbouring cells — and this is the mapping to burn in, because it’s what interviewers actually test: from above (dp[i-1][j] + 1) consumed a source character producing nothing: a deletion. From the left (dp[i][j-1] + 1) produced a target character from nothing: an insertion. From the diagonal (dp[i-1][j-1] + cost) transformed one into the other: substitution, free on a match. The base row and column are pure typing and pure erasing: turning emptiness into a prefix costs its length, and vice versa.

Where the typist analogy breaks: a human corrects words with transpositions — “teh” → “the” feels like one mistake. Levenshtein charges two (or an insert+delete pair); the variant that adds adjacent-swap as a fourth operation is Damerau-Levenshtein, a different recurrence with a different table. Knowing that boundary — which operations your metric actually prices — is exactly the kind of precision the problem rewards.

Loading…

A walkthrough you can check

"cat" → "cut". Base row/column: 0,1,2,3 along each edge.

• Cell (1,1): c = c, free match — diagonal 0.
• Cell (2,2): a vs u, no match — 1 + min(diagonal 0, above 1… left 1) = 1: substitute a→u.
• Cell (3,3): t = t — copies the diagonal: 1.

Distance 1, achieved by one substitution, and the path of cells that produced it reads the edit script backwards. Now "cat" → "at": cell (1,0) is 1 (delete c), and the matches ride the diagonal from there — distance 1, one deletion. The prediction prompts in the visualization ask both flavours: “what value goes in this cell?” (compute the min yourself) and “which operation is cheapest here?” (name the arrow — the question people fail).

The invariant

Every cell is the true minimum edit cost between the prefixes it names, guaranteed by induction: the three predecessors are true (smaller subproblems), the three transitions are exactly the legal operations, and the min over legal options of true costs is a true cost. No estimate ever enters the table — which is why the corner needs no verification pass.

The subtler invariant that makes the metric respectable: edit distance is a genuine metric — zero iff equal, symmetric (every insert one way is a delete the other), and it obeys the triangle inequality (editing A→C can’t beat A→B→C, since concatenated edit scripts are legal scripts). The repo property-tests the triangle inequality over random string triples — a nice example of testing a mathematical property rather than examples.

Complexity, derived

n·m cells, constant work each: O(nm), step-count asserted quadratic in the trace. Space O(nm) full, O(min(n,m)) with two rolling rows for distance-only — with the same reconstruction caveat as LCS (rolling rows lose the arrows; Hirschberg recovers the script in linear space if you truly need both). The bound worth quoting under pressure: the distance is at least |n − m| (length difference must be paid in pure inserts/deletes) and at most max(n, m) (substitute the overlap, insert/delete the rest) — instant sanity checks on any computed answer.

Practical systems rarely fill the whole table: spell-checkers ask “is the distance ≤ k?”, and the banded variant fills only the diagonal strip of width 2k+1 — O(k·min(n,m)) — because any path leaving the band already costs more than k. That optimization is the interview follow-up with the best effort-to-impressiveness ratio in this family.

What people get wrong

Charging for matches. A match copies the diagonal with no +1. Adding cost to matches inflates every distance downstream and is the most common transcription slip.

Two-way min instead of three. Dropping one neighbour (usually the diagonal) still produces plausible numbers — just wrong ones. All three operations compete at every mismatch.

Fuzzing the arrow-to-operation mapping. “Above is… insert?” Under interview pressure the mapping evaporates unless it’s anchored to meaning: above = source consumed, nothing produced = delete. Rebuild it from meaning, not memory.

Claiming O(min(n,m)) space with reconstruction. Distance-only, yes. Script recovery needs the table or Hirschberg — claiming both cheaply is a flag interviewers pull on.

Assuming sub-quadratic exists. Fine-grained complexity theory says truly sub-quadratic edit distance would refute SETH — so “can you do better than O(nm)?” has a real answer: not in general; yes with bounded distance (banding) or approximation. That’s a literature-aware sentence very few candidates own.

Implementation notes across languages

Python: don’t hand-roll in production — difflib approximates ratios, and C-backed packages (rapidfuzz) do exact Levenshtein orders of magnitude faster; hand-roll for interviews with the two-row idiom. Java/C++: int[m+1] prev/curr arrays; in C++ mind that std::min({a, b, c}) (initializer-list form) exists — the nested-min alternative is where the dropped-neighbour bug sneaks in. JavaScript: same aliased-row trap as every JS DP (fill(Array(...)) shares one row); build rows in a loop. Domain coda: bioinformatics runs the scored generalization (Needleman-Wunsch: per-pair substitution costs, gap penalties) — same table, same arrows, richer prices — so this page’s recurrence is also your entry ticket to sequence alignment.