Edit distance — every question, written out
The fewest single-character edits turning one string into another. Three moves per cell: substitute, delete, insert. Spell-check and diff live here.
Read the edit distance explanation and watch it run
What do the two axes of the table mean, and what does a single cell hold?
Invariant identification
Row i and column j are prefix lengths; the cell is the exact cost of turning the first i characters into the first j
Naming the axes as prefix LENGTHS rather than positions is what makes the off-by-one work: row 0 and column 0 mean "the empty prefix", so the table is one larger than each string in each direction. Because every cell is a true minimum rather than an estimate, no verification pass is needed at the end — the bottom-right corner is the answer the moment it is written. Prism labels the rows and columns with the actual characters so the coordinates stay meaningful while you read.
Which edit does each neighbour represent — above, left and diagonal?
Invariant identification
Above is a deletion, left is an insertion, diagonal is a substitution
Rebuild it from meaning rather than memory: a step down a row consumed a source character and produced nothing, which is a deletion; a step right produced a target character from nothing, which is an insertion; a diagonal step advanced both, which is a substitution — free when the characters already match. Interviewers ask about the arrows precisely because the recurrence can be transcribed correctly by someone who cannot explain it. Prism records which neighbour each cell was written from, so the arrow is checkable against the drawing.
Why is the first row filled with 0, 1, 2, 3 rather than zeros?
Edge case reasoning
Turning the empty string into a prefix of length j costs j insertions
The base cases are the only cells whose values come from a direct argument rather than from neighbours, and both are pure typing or pure erasing: emptiness into a prefix costs one insert per character, and a prefix into emptiness costs one delete per character. Zero them out and every distance downstream comes back too small. In an "exactly fill" variant these initialisations change to infinity, which is a good check that you know why they are what they are.
See it run — The base row filling 1, 2, 3 across the top — one insertion per target character.
Without computing anything, what can you say about the distance between a 5-letter and an 9-letter string?
Edge case reasoning
It is at least 4 and at most 9 — the length gap must be paid, and substituting the overlap is a valid upper bound
The lower bound is forced: each edit changes at most one string’s length by one, so closing a gap of four takes at least four operations. The upper bound is constructive: substitute across the five overlapping positions and insert the remaining four. Both are instant sanity checks on any computed answer, and quoting them under pressure costs nothing.
What does this implementation do when the two strings are identical?
Edge case reasoning
Fills the entire table anyway and returns 0 — the diagonal is free, the rest is computed and ignored
Two nested loops with no early exit mean the cost is nm regardless of how similar the strings are — Prism records 170 steps for two identical six-character strings. The diagonal fills with zeros while every cell beside it dutifully computes a mismatch cost nobody will read. That indifference is why the banded variant is a real optimisation and not just a micro-tweak.
See it run — The strings are identical, and the table is still pricing deletions off the diagonal.
Someone writes `dp[i][j] = 1 + dp[i-1][j-1]` for the matching case. What happens?
Code diagnosis
Every distance comes out inflated, because a match is charged as though it were a substitution
A match means the two characters already agree, so the typist does nothing and the cost carries over from the diagonal unchanged — no plus one. This is the most common transcription slip in the whole DP set, and it fails in the direction that looks plausible: distances are still non-negative, still symmetric, just wrong. Test it against a known pair such as kitten and sitting, which must be 3.
See it run — The i-to-i match copies the diagonal value across with no addition at all.
A mismatch is computed as `1 + min(dp[i-1][j], dp[i][j-1])`, dropping the diagonal. What is the effect?
Code diagnosis
Substitution is priced as a delete plus an insert, so distances come out too large on unequal characters
What remains is the longest-common-subsequence metric, where only insertion and deletion exist — a legitimate and different problem. Every cell still fills and every number still looks reasonable, which is why the bug survives casual testing. All three operations compete at every mismatch, and dropping any one of them changes which distance you are computing.
Where does the O(nm) come from, and what is the space?
Complexity derivation
One cell per prefix pair with O(1) work each — nm cells filled, and nm cells stored
Each cell reads at most three already-final neighbours and writes one number, so the work per cell is constant and the total is the cell count. Space matches, at least in this straightforward form. The bound worth knowing beside it: truly sub-quadratic edit distance would refute a standard complexity conjecture, so "can you do better" has a real answer rather than a shrug.
Follow-up: the strings are long. Can you cut the O(nm) memory?
Complexity derivation
Yes — each row reads only the row above and its own left neighbour, so two rows of size min(n,m) suffice
The dependency pattern is strictly local — above, left, and above-left — so a rolling pair of rows carries everything the fill needs, and orienting the shorter string along the rows makes it O(min(n,m)). Java and C++ implementations do exactly this with `prev` and `curr` arrays. In JavaScript, watch the classic aliasing trap: building the rows with a fill of one array object gives you the same row many times.
Follow-up: now the caller wants the actual list of edits, not just the count. What does that cost?
Trade-off & selection
The full table again — walk back from the corner following the neighbour each cell came from
The walk itself is cheap — from the corner, step to whichever neighbour justifies the value, emitting a substitution, deletion or insertion, until you reach the origin — but it needs the cells to still be there. So distance-only can be O(min(n,m)) space and script recovery cannot, unless you use Hirschberg’s divide-and-conquer to get both in linear space. Claiming linear space AND the edit script is a flag interviewers pull on.
The kitten-to-sitting table finishes at 3. Which cell holds that number, and when is it correct?
Trace prediction
The bottom-right cell, and it is exact the instant it is written
The corner names the pair of full prefixes — all six characters of the source, all seven of the target — so it is by definition the answer. Because every cell is a true minimum rather than an estimate, there is no verification phase: the fill ends and the value is final. The trace writes it with the operation that produced it attached, which is an insertion of the trailing g.
See it run — The last cell written: 2 + 1 = 3, arriving from the left, which is an insertion.
A spell-checker only cares whether the distance is at most 2. What changes?
Trade-off & selection
Fill only a diagonal band of width 2k+1, since any path leaving it already costs more than k
Straying j−i positions from the diagonal requires at least that many pure inserts or deletes, so any cell outside a band of width 2k+1 is already over budget and need not be computed. The cost drops to O(k · min(n,m)), which is what makes fuzzy-match indexes practical at scale. This is the highest-value follow-up in the family: two sentences of reasoning for an order-of-magnitude saving.
How does the LCS table differ from this one?
Comparison
LCS allows only insertion and deletion, so it drops the diagonal-substitution option and maximises instead of minimising
The two are close relatives: matches ride the diagonal in both, and mismatches consult above and left in both. What LCS lacks is the substitution move, which is why an edit-distance implementation that forgets the diagonal quietly computes an LCS-flavoured answer. Note the relationship on equal-length strings: LCS length and the insert-delete-only distance determine each other exactly.
A user types "teh" for "the". What does Levenshtein charge, and is that right?
Comparison
Two, because a swap is not one of its three operations — Damerau-Levenshtein adds it as a fourth
Levenshtein is defined over insert, delete and substitute, so a transposition costs two substitutions — arguably wrong for human typing, where a swap feels like one mistake. Damerau-Levenshtein adds an adjacent-swap transition to the recurrence and prices it at one. Knowing which operations your metric actually prices, and being able to say why the boundary matters, is exactly the precision this problem rewards.
"Can you beat O(nm) in general?" What is the honest answer?
Trade-off & selection
Not in general — a truly sub-quadratic algorithm would refute a standard hardness conjecture; band it or approximate instead
Fine-grained complexity shows that a strongly sub-quadratic edit distance would break the Strong Exponential Time Hypothesis, so the quadratic wall is believed to be real rather than a gap in our cleverness. What remains available is structure: bound the distance and band the table, or accept an approximation. Naming the conjecture and then giving the two practical escapes is a literature-aware answer very few candidates own.
Explain the edit-distance table to someone who does not code. Say it out loud first.
Explain it plainly
Imagine a typist with the wrong word in front of them and the right word written on a card, and they may only do three things: delete a letter, type a letter, or overtype one letter with another. You want the fewest moves. The clever part is not the moves, it is refusing to solve the whole thing at once. Instead you build a grid: down the side, "how much of the wrong word have I dealt with", along the top, "how much of the right word have I produced". Every square in that grid asks a tiny question — if I have handled these first four letters and produced those first three, how few moves did that take? And every square’s answer is one move more than the cheapest of the three squares next to it — the one above, the one to the left, and the one diagonally back. Those three squares are literally the three things the typist can do: above means you threw a letter away, left means you typed one in, diagonal means you overtyped. And if the two letters happen to already match, the diagonal is free — you just walk through it. Fill the grid, and the bottom-right corner is your answer. Where the picture breaks: to a human, typing "teh" instead of "the" is one slip. This grid charges two, because swapping two letters is not one of the three moves it knows about. There is a variant that adds swapping as a fourth move, and choosing between them is really choosing what you think a mistake is.
The listener should understand that the grid is a set of small questions whose answers are reused, and that each direction of movement is a specific kind of correction. A strong answer names what the metric refuses to price.