Medium Problemsstringminimization

Edit Distance

Given two strings, find the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into the other.

Do this lesson first: longest common subsequence

Example input

A = "SUNDAY", B = "SATURDAY"

Expected output

3

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j] is the fewest single-letter edits (insert, delete, replace) that turn the first i letters of A = SUNDAY into the first j letters of B, the target. Here m = 6 is A's length and n is how many letters of SATURDAY the slider takes, 8 at the drive size. Row i's own letter is A[i - 1] and column j's is B[j - 1], which is why row 4's gutter reads 4 D and column 3's reads 3 T. The edits run one way, A into B, so a delete removes a letter of A and an insert adds a letter of B. Swap the two words and the number stays the same, but deletes and inserts trade names, and so do the table's two edges.

dp[i][j] = min(dp[i - 1][j - 1] + cost, dp[i - 1][j] + 1, dp[i][j - 1] + 1), where cost = 0 if A[i - 1] = B[j - 1], else 1

Line the two prefixes up the way a cheapest script treats them, each surviving letter of A above the letter of B it becomes, and look at the last column of that alignment. It has one of three shapes. A's last letter sits over B's last letter: kept for free if they are equal, replaced for 1 if not, and the rest turns A's first i - 1 letters into B's first j - 1, so the diagonal, dp[i - 1][j - 1] + cost. A's last letter sits over nothing: it is deleted, for 1, and the rest turns A's first i - 1 letters into all j of B's, so the cell above, dp[i - 1][j] + 1. B's last letter sits under nothing: it is inserted, for 1, and the rest turns all i of A's letters into B's first j - 1, so the cell to the left, dp[i][j - 1] + 1. The cell is the smallest of the three, read in that order: diagonal, up, left, which is keep or replace, delete, insert. On a match the diagonal cannot lose. One extra letter on either word moves the distance by at most 1, since one more delete or insert covers it, so dp[i - 1][j - 1] is at most dp[i - 1][j] + 1 and at most dp[i][j - 1] + 1. This page still reads all three cells at a match and lets the min show it.

Row 0 and column 0 are the cost against an empty word, and they are given rather than computed. dp[0][j] = j, because turning A's empty prefix into B's first j letters takes j inserts: A has no letter to keep or replace, and each edit adds at most one letter. dp[i][0] = i, because turning A's first i letters into nothing takes i deletes. At the drive size that is 15 bases: 9 across row 0 for columns 0 to 8, and 6 more down column 0 for rows 1 to 6. These are not LCS's zeros, and borrowing LCS's zeros is the second trap in the pitfall below. The code panel highlights line 4, the row-0 loop, for every base step, so the bases down column 0, which line 5 writes, light up the line above their own: 6 of the 15 base steps at the drive size, and 6 at every slider length, since SUNDAY keeps its 6 letters. A page names one code line per kind of step, and the two loops stay apart because that is the order the trace writes the bases in, row 0 first and then column 0. Each interior cell reads the cell diagonally up and to the left, the cell above and the cell to its left, so a row-major sweep, left to right within each row, has finished all three before any of them is needed.

Tabulation over all (m + 1) × (n + 1) cells, 63 at the drive size. A memoized top-down solve that asks all three neighbours at each cell reaches all 48 interior cells from dp[6][8], so it saves nothing; one that takes the free diagonal at a match without asking, the safe shortcut from the recurrence panel, reaches 18. A cell reads only the row above and its own row, so two rolling rows of n + 1 cells are enough, and because swapping the words leaves the distance unchanged, the shorter word can go across the top. Drag the slider and B grows one letter at a time while A stays put; the distance goes 4, 5, 5, 5, 4, 3 across lengths 3 to 8. The falls at the end are DAY lining up. At length 6, B's D pairs with SUNDAY's D for dp[4][6] = 3, but A and Y still trail behind it in SUNDAY, and the last cell holds 5. At length 7, B's new A pairs with SUNDAY's A right after that D, so dp[5][7] = 3, three edits from SUNDA to SATURDA, and the last cell only has to delete the Y on top: 3 + 1 = 4. At length 8, B's Y pairs with SUNDAY's Y, a free keep on that same 3: dp[6][8] = 3 + 0 = 3. Here a longer target costs fewer edits, because the letters it adds are ones SUNDAY already ends with, in the same order.

Time O(m × n)Space O(m × n), reducible to O(min(m, n)) with two rolling rows

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 and column 0 are the cost against an empty word, and they are given rather than computed. dp[0][j] = j, because turning A's empty prefix into B's first j letters takes j inserts: A has no letter to keep or replace, and each edit adds at most one letter. dp[i][0] = i, because turning A's first i letters into nothing takes i deletes. At the drive size that is 15 bases: 9 across row 0 for columns 0 to 8, and 6 more down column 0 for rows 1 to 6. These are not LCS's zeros, and borrowing LCS's zeros is the second trap in the pitfall below. The code panel highlights line 4, the row-0 loop, for every base step, so the bases down column 0, which line 5 writes, light up the line above their own: 6 of the 15 base steps at the drive size, and 6 at every slider length, since SUNDAY keeps its 6 letters. A page names one code line per kind of step, and the two loops stay apart because that is the order the trace writes the bases in, row 0 first and then column 0. Each interior cell reads the cell diagonally up and to the left, the cell above and the cell to its left, so a row-major sweep, left to right within each row, has finished all three before any of them is needed.

Rows ↓
Cols →

∅

1 S

2 A

3 T

4 U

5 R

6 D

7 A

8 Y

∅

0

1

2

3

4

5

6

7

8

1 S

1

0

1

2

3

4

5

6

7

2 U

2

1

2

3

4

5

6

3 N

3

2

3

4

5

6

4 D

4

3

4

3

4

5

5 A

5

4

3

4

3

4

6 Y

6

5

4

5

4

3

Rows ↓A: SUNDAY

Cols →B: the first n letters of SATURDAY

edit-distance.ts

1function editDistance(a, b) {
2 const m = a.length, n = b.length;
3 const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
4 for (let j = 0; j <= n; j++) dp[0][j] = j; // j inserts
5 for (let i = 0; i <= m; i++) dp[i][0] = i; // i deletes
6 for (let i = 1; i <= m; i++) {
7 for (let j = 1; j <= n; j++) {
8 const cost = a[i - 1] === b[j - 1] ? 0 : 1;
9 dp[i][j] = Math.min(
10 dp[i - 1][j - 1] + cost, // keep or replace
11 dp[i - 1][j] + 1, // delete a[i - 1]
12 dp[i][j - 1] + 1, // insert b[j - 1]
13 );
14 }
15 }
16 return dp[m][n];
17}

Base caseComputedBeing readAnswer

The code, the trap, the variations

edit-distance.ts

1function editDistance(a, b) {
2 const m = a.length, n = b.length;
3 const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
4 for (let j = 0; j <= n; j++) dp[0][j] = j; // j inserts
5 for (let i = 0; i <= m; i++) dp[i][0] = i; // i deletes
6 for (let i = 1; i <= m; i++) {
7 for (let j = 1; j <= n; j++) {
8 const cost = a[i - 1] === b[j - 1] ? 0 : 1;
9 dp[i][j] = Math.min(
10 dp[i - 1][j - 1] + cost, // keep or replace
11 dp[i - 1][j] + 1, // delete a[i - 1]
12 dp[i][j - 1] + 1, // insert b[j - 1]
13 );
14 }
15 }
16 return dp[m][n];
17}

Where people go wrong

Dropping the + 1 from the diagonal on a mismatch, so the diagonal is dp[i - 1][j - 1] whatever the letters and every replacement is free. At length 6 the result is plainly absurd: SUNDAY and SATURD both have six letters, the free diagonal runs from dp[0][0] to dp[6][6] without paying once, and the table answers 0, as if the two words were already equal. The real answer there is 5. Across the slider the broken rule gives 3, 2, 1, 0, 1, 2 against the real 4, 5, 5, 5, 4, 3, wrong at every length, including 2 against 3 at the drive size. The second trap is borrowing LCS's bases. A row 0 and column 0 of zeros say an empty word grows into SATURDAY for free, and the table built on them gives 2, 3, 4, 4, 3, 2, also wrong at every length.

Allow only insertions and deletions, no replacement.
The replace option goes, so a mismatch becomes min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), while a match still takes the diagonal for free. The bases do not change, since they were already pure inserts or pure deletes. The answer then has a closed form in the longest common subsequence: keep it, delete the rest of A, insert the rest of B, for |A| + |B| - 2 × LCS. Here the longest common subsequence is SUDAY, 5 letters, so the count is 6 + 8 - 10 = 4 at the drive size, one more than the real 3, because replacing N with R now costs a delete plus an insert. This is the closing variation of the longest-common-subsequence page, reached from the other side.
Give the three operations their own prices: rep per replacement, del per delete, ins per insert.
Each candidate adds its own price instead of 1: dp[i - 1][j - 1] + (0 on a match, rep otherwise), dp[i - 1][j] + del, dp[i][j - 1] + ins. The bases change too, to dp[0][j] = j × ins and dp[i][0] = i × del, because each edge is a run of a single kind of edit. The min of three candidates and the row-major sweep stay. Price a replacement at 2 with inserts and deletes at 1 and a replacement can only tie a delete plus an insert, never beat it, so the answers become the insert-and-delete-only ones from the variation above: 5, 6, 7, 6, 5, 4 across the slider, 4 at the drive size.
Also allow swapping two adjacent letters as a single edit (the Damerau transposition).
A fourth candidate joins the min, two back on both axes: dp[i - 2][j - 2] + 1, offered only when A's last two letters are B's last two in swapped order, A[i - 1] = B[j - 2] and A[i - 2] = B[j - 1]. The bases do not change, and the other three candidates stay as they are, but a cell now reaches two rows up, so rolling storage needs three rows instead of two. This restricted form, often called optimal string alignment, never edits a swapped pair a second time. On this pair the fourth candidate is never offered: no two adjacent letters of SUNDAY appear swapped and adjacent in any prefix of SATURDAY, so the answers stay 4, 5, 5, 5, 4, 3. Against the target SUNDYA it matters: one swap where this page's rules need two edits.

Longest Increasing Subsequence Largest Divisible Subset