Worked examples — DP problems — edit distance (Levenshtein)

This page hunts down every kind of input edit distance can throw at you and works each one from the ground up. If the parent note taught you the machine, this page is the stress test — we feed it empty strings, identical strings, single characters, strings where every letter is wrong, a real-world spell-checker, and an exam twist, so you never hit a case you haven't already seen filled in.

First, three symbols must be earned before anything else uses them: the two strings $A$ and $B$, and the distance function $d$.

Now the rule that drives everything (built fully in the parent note):

Here "first $i$ letters" means: chop the string after position $i$. For $A=$cat, the "first 2 letters" are ca. The letter we are currently deciding about is $A[i-1]$ — the last one in that chop. That $-1$ is the single most common bug, so we will name the current letters out loud in every example.

---

The scenario matrix

Every edit-distance problem falls into one of these case classes. Our job below is to fill every row with a fully worked example. (Recall $m=|A|$, $n=|B|$ from the definitions above.)

#	Case class	What makes it special	Covered by
C1	Both empty	Degenerate: nothing to do	Example 1
C2	One empty, one non-empty	Pure base case (all inserts or all deletes)	Example 1
C3	Identical strings	Every char matches — diagonal carries 0	Example 2
C4	Single-char, equal vs unequal	Smallest non-empty case, both branches	Example 3
C5	Equal length, some substitutions	Distance from swaps only, no length change	Example 4
C6	Different length, mixed ops	Insert/delete and substitute together	Example 5
C7	Completely disjoint alphabets	Worst case — distance $=\max (m,n)$	Example 6
C8	Prefix/suffix contained	One string sits inside the other	Example 7
C9	Real-world word problem	Spell-checker suggestion cost	Example 8
C10	Exam twist: multiple optimal paths	Same distance, different edit scripts	Example 9

We also lean on a sanity bound used throughout: the distance is always between $|m-n|$ (the length gap — a lower bound, because you cannot avoid closing the gap) and $\max (m,n)$ (the length of the longer string — an upper bound, because worst case you fix one letter of it per op). In symbols:

$|m-n|\le d(A,B)\le \max (m,n)$

We will re-check this band in every example below — it is the fastest way to catch an arithmetic slip.

The figure below plots this band on a number line, with the real distance (red dot) trapped inside it for the sunday→saturday example we solve in Example 5.

Figure s01 — a horizontal number line from $0$ to $8$. A black double-headed arrow spans the allowed band from the lower bound $|m-n|=2$ to the upper bound $\max (m,n)=8$. The red dot marks the actual answer $d=3$, sitting inside the band. Read it as: no legal distance can fall left of $2$ or right of $8$. We return to this exact picture in Example 5.

---

Example 1 — Empty strings (C1 + C2)

Forecast: Before reading on, guess all three. Empty→empty feels like… nothing. Empty→3-letter feels like… 3 builds. 3-letter→empty feels like… 3 removals.

Steps.

1. $d(\text{""},\text{""})=dp[0][0]=0$ (using $d(A,B)=dp[|A|][|B|]$ with both lengths $0$). Why this step? Two empty strings are already identical; zero moves. This is the seed every table grows from.
2. $d(\text{""},\text{"cat"})=dp[0][3]$. The base-case rule says $dp[0][j]=j$, so $dp[0][3]=3$. Why this step? From nothing you can only insert. To produce c, then a, then t, you insert three times — there is no cheaper move because deletes and substitutions need an existing letter to act on.
3. $d(\text{"dog"},\text{""})=dp[3][0]$. The base-case rule says $dp[i][0]=i$, so $dp[3][0]=3$. Why this step? To reach the empty string you can only delete — remove d, o, g, three deletes.

Verify: For the middle case, $m=|\text{""}|=0$, $n=|\text{"cat"}|=3$. Lower bound $|m-n|=|0-3|=3$; upper bound $\max (0,3)=3$. The answer $3$ is pinched exactly between them, so it must be right. ✅ (The dog→"" case is the mirror image, $|3-0|=3=\max$.)

---

Example 2 — Identical strings (C3)

Forecast: Same word, both sides. Guess the number before continuing.

Steps.

1. $A=B=$apple, so $m=|A|=5$ and $n=|B|=5$ — equal lengths. Fill the diagonal. At $dp[1][1]$: current letters $A[0]=$a, $B[0]=$a — they match, so $dp[1][1]=dp[0][0]=0$. Why this step? A match copies the diagonal with no +1 (the "match" branch). Zero cost carries through.
2. Each subsequent diagonal cell matches (p=p, p=p, l=l, e=e), so $dp[2][2]=dp[3][3]=dp[4][4]=dp[5][5]=0$. Why this step? Every current-letter pair is equal, so each step re-copies $0$ down the diagonal. Look at the straight red diagonal of $0$s in the figure below.
3. Final answer $d(A,B)=dp[5][5]=0$.

Figure s02 — the full $6\times 6$ DP table for apple→apple. Columns are headed by B=apple, rows by A=apple. The base row and column count up $0,1,2,3,4,5$ in black. The red diagonal of $0$s runs from top-left to bottom-right; the red arrow points at the answer $dp[5][5]=0$. Every matched letter copies the cell up-and-left, so zeros ride straight down.

Verify: Distance $0$ means "already equal" — and the strings are identical, so no edits are possible or needed. Sanity band: $|m-n|=|5-5|=0\le 0\le \max (5,5)=5$. The answer sits on the lower bound, exactly where identical strings should. ✅

---

Example 3 — Single characters, both branches (C4)

Forecast: One is a match, one is a mismatch. One should cost $0$, the other should cost $1$ — which is which?

Steps for "a"→"a".

1. Table is $2\times 2$. Bases: $dp[0][0]=0$, $dp[0][1]=1$, $dp[1][0]=1$. Why this step? Row 0 and column 0 must exist before we touch $dp[1][1]$ — that is the "forgot the base" mistake from the parent note.
2. $dp[1][1]$: current letters $A[0]=$a, $B[0]=$a match → $dp[1][1]=dp[0][0]=0$. So $d(\text{"a"},\text{"a"})=0$. Why this step? Match branch, pure diagonal, no +1.

Steps for "a"→"b".

3. $dp[1][1]$: $A[0]=$a, $B[0]=$b differ → $1+\min (dp[0][0],dp[0][1],dp[1][0])=1+\min (0,1,1)=1$. So $d(\text{"a"},\text{"b"})=1$. Why this step? The cheapest predecessor is the diagonal $dp[0][0]=0$, meaning we substitute a→b for one coin (Levenshtein's substitute operation — not a transposition; there is no "swap two letters" move in Levenshtein). Deleting a then inserting b would cost $2$ — the min correctly rejects it.

Verify: "a"→"a" gives $0$; sanity band $|1-1|=0\le 0\le \max (1,1)=1$. ✅ "a"→"b" gives $1$; band $0\le 1\le 1$, and since $m=n=1$ the whole cost is one substitution, never a length change. ✅

---

Example 4 — Equal length, substitutions only (C5)

Forecast: Both strings in each pair have equal length. Guess: does equal length force the answer to be pure substitutions?

Steps for "cat"→"cot". Here $m=n=3$.

1. $dp[1][1]$: c=c match → $dp[1][1]=dp[0][0]=0$. Why this step? Match branch carries $0$ forward.
2. $dp[2][2]$: current letters $A[1]=$a, $B[1]=$o differ → $1+\min (dp[1][1],dp[1][2],dp[2][1])=1+\min (0,1,1)=1$. Why this step? The min picks the diagonal predecessor $dp[1][1]=0$, i.e. substitute a→o. The delete path ($dp[1][2]$) and insert path ($dp[2][1]$) both cost $1$, so $1+1=2$ each — the recurrence rejects them because substitution here is strictly cheaper. This is the "why substitute, not delete+insert" the formula settles automatically.
3. $dp[3][3]$: t=t match → $dp[3][3]=dp[2][2]=1$. So $d(\text{"cat"},\text{"cot"})=1$.

Steps for "abcd"→"wxyz". Here $m=n=4$.

4. Every diagonal cell has differing letters (a≠w, b≠x, c≠y, d≠z). At each, the diagonal predecessor beats the delete/insert neighbours by exactly the same $1$-vs-$2$ margin as Step 2, so each contributes one substitution: $dp[1][1]=1$, $dp[2][2]=2$, $dp[3][3]=3$, $dp[4][4]=4$. Why this step? When lengths are equal, the min-over-three at every diagonal cell always favours substitution (cost $1$) over a delete+insert pair (cost $2$). Hence $4$ substitutions total.

Verify: "cat"→"cot" gives $1$; sanity band $|3-3|=0\le 1\le \max (3,3)=3$. ✅ "abcd"→"wxyz" gives $4$; band $0\le 4\le 4$ — it sits on the upper bound because every letter needed work. ✅

---

Example 5 — Different length, mixed operations (C6)

Forecast: These share s…day. Guess how many of the $8$ target letters need real work.

Steps.

1. Fill the DP table row by row (rows = sunday, columns = saturday). The table below is computed by the recurrence; trace the red back-pointer path from the bottom-right answer up to the top-left corner.

Figure s03 — the $7\times 9$ DP table for sunday→saturday. Rows headed by A=sunday, columns by B=saturday. The bottom-right cell holds the answer $3$. The red staircase traces one optimal back-pointer path from $dp[6][8]$ to $dp[0][0]$: diagonal moves on matched letters (free) and the three costly moves — two inserts and one substitute.

2. The shared letters s…u…d-a-y line up on the diagonal for free — these are the diagonal steps of the red path where letters match. What is left: saturday has an extra a and t that sunday lacks → insert 2 (two leftward steps in the path). And sunday's n must become r → substitute 1 (one diagonal step where letters differ). Why this step? Matches are free, so the free diagonal run traces out a set of positions that agree in order between the two strings. This is where the LCS connection is precise: the free (match) diagonal steps form one common subsequence — but plain Levenshtein does not maximise it. Two related but different DPs: LCS counts matches to maximise; Levenshtein counts edits to minimise, and only when substitution and insert/delete all cost $1$ do they satisfy the identity $d(A,B)=m+n-2\cdot \text{LCS}(A,B)$ for the substitution-free (LCS) edit model. We do not rely on that identity here; we just observe that longer shared runs shrink the distance.
3. Total $=2+1=3$.

Verify: Back to Figure s01, whose band was built for this example: lower bound $|m-n|=|6-8|=2$; our answer $3>2$ (the extra $1$ is the forced substitution), and $3\le \max (6,8)=8$. The red dot in s01 sits at exactly $3$, inside the band. ✅

---

Example 6 — Disjoint alphabets, worst case (C7)

Forecast: No letters in common, and lengths $3$ vs $4$. Guess whether the answer is $\max (3,4)$.

Steps.

1. Since nothing matches, every cell falls into the "differ" branch — no free diagonals exist. The table below shows the whole grid; the answer is the bottom-right cell.

Figure s04 — the $4\times 5$ DP table for abc→xyzw with fully disjoint letters. Rows headed A=abc, columns B=xyzw. Because no letters match, values only ever grow; the red bottom-right cell shows the answer $4$, equal to $\max (m,n)$. The red path is a mix of three substitutions and one insert.

2. Reading the path: substitute a→x, b→y, c→z (three substitutions), then insert w — total $3+1=4$. Why this step? When the alphabets are disjoint, no free matches exist, so the distance hits its ceiling: the longer string's length. You spend one op per letter of the longer string.

Verify: Sanity band $|m-n|=|3-4|=1\le 4\le \max (3,4)=4$. ✅ The disjoint case saturates the upper bound exactly — no input of these lengths can cost more than $4$.

---

Example 7 — One string is a substring of the other (C8)

Forecast: In the first, is cat hiding inside cart? In the second, is cat a chunk of scatter? Guess each distance from the "extra letters" alone.

Steps for "cart"→"cat". Here $m=4$, $n=3$.

1. The DP table below (top panel) shows the alignment. Follow the red path: c matches c, a matches a (diagonal, free), then cart still has r before its t while cat goes straight to t — the r is a leftover → delete it (one upward step).

Figure s05 — two stacked DP tables, each with its axes labelled. Top: $5\times 4$ table for cart→cat; the left axis is labelled A=cart (rows), the top axis B=cat (cols), and the base row/column ($0,1,2,3$) are annotated. The red path shows two free diagonal matches then one upward delete step, answer $1$. Bottom: $4\times 8$ table for cat→scatter; left axis A=cat (rows), top axis B=scatter (cols), base row/column annotated. The red path shows a free diagonal run through cat bracketed by leftward insert steps for s and ter, answer $4$.

2. So one extra letter r → distance $1$.

Steps for "cat"→"scatter". Here $m=3$, $n=7$.

3. scatter = s + cat + ter. We must insert s at the front and t,e,r at the back → $1+3=4$ inserts. All of cat matches for free in the middle (the free diagonal run in the bottom table). Why this step? When one string contains the other's letters in order plus extras, each extra is a single delete/insert.

Verify: "cart"→"cat": sanity band $|m-n|=|4-3|=1\le 1\le \max (4,3)=4$ — the answer sits on the lower bound because only deletions were needed. ✅ "cat"→"scatter": band $|3-7|=4\le 4\le \max (3,7)=7$ — again on the lower bound, pure insertions, no substitution since cat embeds cleanly. ✅

---

Example 8 — Real-world word problem: spell-checker (C9)

Forecast: Both candidates are $7$ letters, same as the typo. Guess which correction is "closer".

Steps.

1. Both candidate distances come from filling a DP table; the figure shows the two answer cells side by side so you can see which is smaller.

Figure s06 — two DP tables, one per candidate. Left: recieve→receive, its bottom-right answer cell in red reads $2$. Right: recieve→relieve, its red answer cell reads $1$. The smaller red number wins the ranking.

2. "recieve" → "receive": equal lengths ($m=n=7$), so align letter-for-letter. r-e-c match, then the typo has i-e where the correct word has e-i — reversed, so two substitutions (i→e and e→i), then v-e match. Distance $2$. Why this step? Equal lengths → align position-by-position; two positions differ → two substitutions.
3. "recieve" → "relieve": r-e match, then c vs l differ (+1 substitute), i-e-v-e all match. Only one position differs → distance $1$.
4. Compare: receive costs $2$, relieve costs $1$. The checker ranks "relieve" first by raw edit distance. Why this step matters? Real spell-checkers add a dictionary-frequency tie-breaker precisely because raw distance can favour the "wrong" word — but on pure Levenshtein, relieve wins.

Verify: All three words have length $7$. receive: band $|7-7|=0\le 2\le 7$; relieve: band $0\le 1\le 7$. Both distances are pure-substitution counts ($2$ and $1$) since $m=n$. ✅

---

Example 9 — Exam twist: two optimal paths, same distance (C10)

Forecast: The letters are the same, just reordered. Levenshtein has no transposition operation (you cannot swap two letters in one move), so a reorder isn't free — guess the cost.

Steps.

1. Build the $3\times 3$ table ($m=n=2$). Bases: $dp[0][\cdot ]=0,1,2$ and $dp[\cdot ][0]=0,1,2$. Then $dp[1][1]=1$ (a≠b, substitute), $dp[1][2]=1$ (a=a match, carries $dp[0][1]=1$), $dp[2][1]=1$ (b=b match, carries $dp[1][0]=1$), and $dp[2][2]=1+\min (dp[1][1],dp[1][2],dp[2][1])=1+\min (1,1,1)=2$.

Figure s07 — the $3\times 3$ DP table for ab→ba, answer $2$ in the red bottom-right cell. Three red arrows fan out of that cell to all three predecessors ($dp[1][1]$, $dp[1][2]$, $dp[2][1]$), which all tie at $1$. Because three back-pointers are equally optimal, more than one edit script achieves the minimum.

2. At $dp[2][2]$ all three predecessors tie at $1$, so the figure draws three red back-pointer arrows — that tie is exactly why multiple optimal edit scripts exist. Two natural scripts:
   • Substitute a→b, then substitute b→a.
   • Delete a, then insert a at the end (a "rotate" done as delete+insert). Both cost $2$. Why this step? Each distinct back-pointer path from bottom-right to top-left decodes into a distinct edit script of the same total cost.

Verify: Levenshtein has no transposition operation, so swapping two adjacent letters costs $2$, not $1$. Sanity band $|m-n|=|2-2|=0\le 2\le \max (2,2)=2$ — sits on the upper bound. ✅ (If transpositions were allowed — the Damerau–Levenshtein variant — the answer would be $1$; standard Levenshtein gives $2$.)

---

Recall Quick self-test across the matrix

Cover the answers and reconstruct each. $d(\text{""},\text{""})$ ::: $0$ $d(\text{""},\text{"cat"})$ ::: $3$ (three inserts) $d(\text{"apple"},\text{"apple"})$ ::: $0$ (identical) $d(\text{"a"},\text{"b"})$ ::: $1$ (one substitution) $d(\text{"cat"},\text{"cot"})$ ::: $1$ (one substitution) $d(\text{"abcd"},\text{"wxyz"})$ ::: $4$ (four substitutions) $d(\text{"sunday"},\text{"saturday"})$ ::: $3$ $d(\text{"abc"},\text{"xyzw"})$ ::: $4$ (worst case $=\max$) $d(\text{"cart"},\text{"cat"})$ ::: $1$ (delete r) $d(\text{"cat"},\text{"scatter"})$ ::: $4$ (four inserts) $d(\text{"recieve"},\text{"relieve"})$ ::: $1$ $d(\text{"ab"},\text{"ba"})$ ::: $2$ (no free transposition)

---

Connections

• Parent: Edit Distance — the machine these examples stress-test.
• Longest Common Subsequence — the free diagonal run relates to a shared subsequence (Example 5), though LCS maximises matches while Levenshtein minimises edits.
• Sequence Alignment — spell-checking (Example 8) is small-scale alignment.
• Optimal Substructure · Overlapping Subproblems — why the recurrence is correct on every case above.
• Recursion and Memoization — the top-down way to compute any of these.
• Space Optimization in DP — every table above needs only the previous row.
• Dynamic Programming — the umbrella paradigm.