Edit distance and string DP

Why it matters

Spell checkers, search suggestions, DNA comparison and version control all need one question answered: how different are two strings? Edit distance is the classic measure of that difference, and it is one of the most frequently asked DP questions in interviews. It is also a good test of everything in this module, because it needs a two-dimensional table, a careful base case, a three-way choice at each cell, and a clear idea of what each cell means.

The second problem in this lesson, the longest palindromic substring, uses the same kind of table, but the cells hold true or false instead of numbers. It also shows a pattern that appears in many string problems: a cell depends on a smaller piece of the same string, so the loops must go in an order that fills the smaller piece first.

Part 1: edit distance

The edit distance between two strings is the fewest single-letter operations that turn the first string into the second. There are three operations. You can insert a letter, which adds one letter somewhere. You can delete a letter, which removes one. You can replace a letter, which swaps one letter for another. Each operation counts as one step.

A spell checker uses this idea directly. The misspelling kiten is one insertion away from kitten, so the checker can suggest kitten as a likely correction. A search box uses it to match a query like sitten to sitting even when the spelling is not exact. A DNA tool uses it to measure how far apart two sequences are.

Take kitten and sitting. A good first guess is three steps. Replace the first k with s, giving sitten. Replace the e with i, giving sittin. Insert a g at the end, giving sitting. Three operations is the best possible here, so the edit distance is 3. The rest of this part shows how a table finds that answer without you having to guess.

What a cell means

Let dp[i][j] be the edit distance between the first i letters of a and the first j letters of b. Here a and b are the two strings. The table therefore has n + 1 rows and m + 1 columns, where n and m are the lengths. The extra row and column stand for the empty prefix.

Write this definition as the first line of your code comment before anything else. A wrong definition is the most common cause of wrong edit distance code, and a clear definition makes the rest easy to check.

The base cases

The base cases are the empty prefixes. Turning the empty string into the first j letters of b takes exactly j insertions, so dp[0][j] = j. Turning the first i letters of a into the empty string takes i deletions, so dp[i][0] = i. Those two edges are the first thing to fill in.

Forgetting the base cases is a common mistake. If the edges stay at zero, the table claims that an empty string is one edit away from any string, and every answer comes out too small.

The recurrence

Now look at the last letters of the two prefixes, a[i - 1] and b[j - 1]. There are two cases.

If the letters match, no operation is needed for them. The edit distance is the distance of the shorter prefixes, so dp[i][j] = dp[i - 1][j - 1]. It is never worse to match two equal letters than to pay for them, and this case always wins.

If the letters differ, you must spend one operation on the last position, and there are three ways to do it. Replace a[i - 1] with b[j - 1], which leaves the prefixes i - 1 and j - 1. Delete a[i - 1], which leaves i - 1 letters of a against all j letters of b. Or insert b[j - 1] after a's prefix, which leaves all i letters of a against j - 1 letters of b. Take the smallest of the three and add 1:

dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])

Each of the three neighbours matches one operation. The diagonal neighbour is a replacement, the cell above is a deletion from a, and the cell to the left is an insertion into a. A loop that goes row by row fills all three before the cell itself, so the order is correct.

The table

The next diagram shows the full table for kitten and sitting. Rows are the letters of kitten, and columns are the letters of sitting. The dash marks the empty prefix, so the first row and column hold the base cases 0 to 7 and 0 to 6.

Edit distance table for kitten against sitting with rows and columns labelled by letters and the bottom right cell highlighted as 3

Check a few cells against the rule. The cell for k against s differs, so it is 1 plus the smallest of the diagonal (0), the cell above (1) and the cell to the left (1), which gives 1. The cell for ki against si matches on the i, so it takes the diagonal cell for k against s, which is 1. The cell for kit against sit matches on the t, so it is the diagonal cell for ki against si, which is 1. Those matching cells are where the table saves work, and they explain why the kitten column for i ends up small.

Now trace the answer. The bottom right cell is 3. It comes from the cell to its left, which is kitten against sittin with value 2, plus 1 for inserting the g. That agrees with the three operations we found by hand. The table records the answer, and a trace back through it recovers the operations.

The Viz below steps through the same table cell by cell. Watch for the moments when the letters match, because those are the cells that copy the diagonal and cost nothing.

The program

Here is the complete edit distance program. It reads the two words on separate lines and prints the distance.

Type kitten in the Input box, press Enter, type sitting on the next line, and press Run.

Output:

edit distance = 3

The min function here takes a braced list of three values. That form is part of the <algorithm> header, so the include is required. The next section shows what happens without it.

Complexity. The table has (n + 1) times (m + 1) cells, and each does constant work. So the time is O(n times m), and so is the space for this version.

Recovering the operations

Often the question is not only "how many operations" but "which operations". To find them, walk back from the bottom right cell, using the same three neighbours that the recurrence used. At each cell, if the letters match and the diagonal gives the value, move diagonally with no operation. Otherwise, look at which neighbour gave the minimum. A diagonal move that changed the letter is a replacement. A move up is a deletion from a. A move left is an insertion into a. Stop when you reach the top or left edge, and the remaining letters are inserted or deleted in one block.

Walking back through the kitten table gives the three operations we found by hand, in reverse order. The last move was an insertion of g, the previous one replaced e with i, and the first replaced k with s. The table holds all the information, so you can always rebuild the steps from it. The trace is also the answer to the interview follow-up "show me the edits", so practise it with a pencil on a small table.

Using two rows

The table in the program stores every cell, which costs O(n times m) memory. For two words of 5,000 letters each, that is 25 million integers, about 100 megabytes, which is too much for many programs. The table does not need to be that large. A cell reads only the cell above it, the cell to the left, and the diagonal. The diagonal sits in the row above. So once a row is finished, the row before it is never read again.

That means two rows are enough. Keep one row for the row you are building and one for the row above. After finishing a row, the new row becomes the old row. The only subtle point is the diagonal value. When you overwrite a cell, you lose the old value that the next cell in the row needs as its diagonal. The fix is to save the old diagonal in a variable before you overwrite each cell.

Here is the two-row version. It reads two words and prints the distance, the same answer as the full table.

Type sunday in the Input box, press Enter, type saturday on the next line, and press Run.

Output:

edit distance = 3

This version uses a vector of length m + 1 for each of two rows, so the memory is O(m). The swap call exchanges the two vectors in constant time, because it swaps their internal pointers rather than copying the numbers. After the loop, prev holds the last row, and its last entry is the answer.

Notice that this version does not keep cur[j - 1] as a diagonal. It reads cur[j - 1] as the cell to the left, which is correct because that cell was just written in the same row. It reads prev[j - 1] as the diagonal, which is still the old row. The two reads come from two different rows, and that is why nothing is overwritten too early.

Part 2: the longest palindromic substring

A palindrome reads the same forwards and backwards, such as racecar or aba. A substring is a block of consecutive letters, so the longest palindromic substring of a string is the longest palindrome you can find as one unbroken piece. For babad, the answer is 3, because bab and aba are both palindromes of length 3. For cbbd, the answer is 2, from bb.

Let pal[i][j] be true when the piece of the string from position i to position j, both included, is a palindrome. The base cases are pieces of one letter, which are always palindromes, and pieces of two letters, which are palindromes when both letters match.

For longer pieces, the outer letters must match, and the inside must be a palindrome. The inside is the piece from i + 1 to j - 1. So:

pal[i][j] = (s[i] == s[j]) and pal[i + 1][j - 1]

The inside check only applies when the piece is long enough to have an inside, which means at least three letters. For a two-letter piece, the matching of the two letters is the whole test. Forgetting that special case reads a cell that does not exist, and it is a common bug in this problem.

The loop order

The recurrence reads pal[i + 1][j - 1], a piece that starts one position later. So the piece starting at i + 1 must be filled before the piece starting at i. That means the outer loop must go from the end of the string down to the start, and the inner loop goes from i up to the end. The loop direction follows from what the recurrence reads, which is the rule from the last lesson.

A worked trace

Take babad, with positions 0 to 4. Start at i = 4. The piece d is a palindrome, so pal[4][4] is true. Move to i = 3: pal[3][3] is true for a, and the piece ad fails because a and d differ. Move to i = 2: pal[2][2] is true for b, the piece ba fails, and bad fails because b and d differ. Move to i = 1: pal[1][1] is true for a, and ab fails. The piece from 1 to 3, which is aba, has matching outer letters, and its inside pal[2][2] is true, so pal[1][3] is true with length 3. Finally, i = 0: the piece from 0 to 2, which is bab, has matching outer letters, and its inside pal[1][1] is true, so pal[0][2] is also true with length 3. The longest found is 3.

Notice how the answer grows. Each new piece uses a smaller inside that was already computed, because the loop has moved on from the larger starting positions. This is the same pattern as the LCS table, applied to a single string.

The Viz below steps through a palindrome table. Its cells are numbers, not booleans, but the reads of smaller pieces follow the same order, so use it to check the loop direction.

The program

Here is the complete program. It reads one word and prints the length of the longest palindromic substring.

Type babad in the Input box and press Run.

Output:

longest palindrome length = 3

The condition j - i < 2 handles the one-letter and two-letter pieces. For a one-letter piece, j equals i, and the test s[i] == s[j] is trivially true. For a two-letter piece, j - i is 1, and the test is only that the two letters match. Only pieces of three or more letters read the inside cell, and that cell always exists.

Complexity. The table has n squared cells, and each does constant work, so the time is O(n squared). The space is also O(n squared) for the table, and the cell type vector<bool> keeps each entry to one bit. The next section explains a version that uses far less memory.

Part 3: reading and checking a table

When a DP program gives a wrong answer, a printed table is the fastest tool. The next program prints the full edit distance table, the same one as the diagram, with each row labelled by a letter of the first word. It is a good template to keep for debugging.

Type kitten in the Input box, press Enter, type sitting on the next line, and press Run.

Output:

    -  s  i  t  t  i  n  g
 -  0  1  2  3  4  5  6  7
 k  1  1  2  3  4  5  6  7
 i  2  2  1  2  3  4  5  6
 t  3  3  2  1  2  3  4  5
 t  4  4  3  2  1  2  3  4
 e  5  5  4  3  2  2  3  4
 n  6  6  5  4  3  3  2  3
edit distance = 3

The setw function from <iomanip> pads each value to a fixed width, so the columns line up. Without it, numbers of different widths would drift out of line, and the table would be hard to read. The header row lines up with the numbers below it because both use the same width.

Read the output as a grid, and compare it with the diagram. The bottom right value is 3. The first row and first column are the base cases. Every other cell is either a copy of the diagonal (where the letters match, such as the i in row i and column i) or one more than the smallest neighbour. If the printed table disagrees with your hand trace at a cell, look at the letters that cell compares, and then at its three neighbours.

Thinking of the table as a route

Another way to see edit distance is as a route through the table. Start at the top left corner, cell (0, 0), and finish at the bottom right corner. Each move takes you one step right, one step down, or one step diagonally down and right. A step down is a deletion of a letter from a. A step right is an insertion of a letter from b. A diagonal step is a match, which is free, or a replacement, which costs 1.

The edit distance is the cheapest route. Every route describes one complete way to turn a into b, and the cost of the route is the number of operations it contains. The table is simply the cheapest cost to reach each cell, filled in as the route options become known. The recurrence is the rule that the cheapest route into a cell comes from one of its three neighbours, plus the cost of the last step.

Now read the route for kitten and sitting from the walk-back. Start at (0, 0). Diagonal to (1, 1) is a replacement, k to s, cost 1. Diagonal to (2, 2) is a match on i, cost 0. Diagonal to (3, 3) is a match on t, cost 0. Diagonal to (4, 4) is a match on the second t, cost 0. Diagonal to (5, 5) is a replacement, e to i, cost 1. Diagonal to (6, 6) is a match on n, cost 0. Right to (6, 7) is an insertion of g, cost 1. The total is 3, and the route has the same three operations as the hand trace.

This view makes some facts obvious. A route with a diagonal match costs nothing, so the cheapest route prefers matches. A route that goes along the top edge only inserts letters, and one that goes down the left edge only deletes them. The answer can never be more than the length of the longer word, because the route that does nothing but replace and insert or delete never costs more than that.

Talking through it in an interview

Interviewers often want to hear your reasoning, not only the final code. A clear way to talk through edit distance has four parts, and you can say them in about a minute before you write anything.

First, restate the problem with a small example. Say that the edit distance counts inserts, deletes and replaces, and that kitten to sitting is 3.

Second, define the state. Say that dp[i][j] is the distance between the first i letters of one word and the first j letters of the other. This sentence is what the interviewer will check your code against.

Third, give the three rules. Say that a match copies the diagonal, and a mismatch costs one more than the smallest of the three neighbours. Name what each neighbour means: the diagonal is a replacement, the cell above is a deletion, and the cell to the left is an insertion.

Fourth, state the cost. Say that the time is O(n times m) and the space is O(n times m), and that the space can drop to O(m) because each row reads only the row above.

If you do this in order, the interviewer can follow the logic even if you make a small slip while writing the code. Make a habit of stating each step before you take it, because that is also how you catch your own mistakes.

How to approach any DP problem

The five steps from the earlier lessons apply to every string problem in this module. Here they are in the order you should use them.

1. Say what one state means, in a sentence, before you write code. For edit distance it is the distance between two prefixes.
2. Write the base cases, which are usually the empty prefixes or the single letters.
3. Write the recurrence, with a clear rule for the match case and the mismatch case.
4. Pick the loop order so that every cell the recurrence reads is already filled.
5. Check the table with a small input that you can work out by hand, and print the table when the answer is wrong.

Keep the state definition in a comment at the top of the code. If you later change a loop bound or an index, that comment tells you what the index is supposed to mean.

What happens inside

Memory is the main cost of string DP, so it helps to know the numbers. A table of ints for two strings of length 1,000 has about 1,000,000 cells. Each int takes four bytes, so the table is about 4 megabytes. That is comfortable. A table of length 10,000 needs about 400 megabytes, which might be too much. The two-row version drops that to two rows of length m, so for the same input it needs only about 80 kilobytes.

A vector<bool> for the palindrome table stores one bit per cell. A table of length 10,000 then needs about 12.5 megabytes. Even so, the table grows with the square of the length, which is why the next idea matters for long inputs.

Time also grows with the square of the length. Doubling the input multiplies the work by four. For strings of 1,000 letters, that is a million cells, which runs in a few milliseconds. For strings of 100,000, it is ten billion cells, which is too slow. For long strings, the problem usually needs a different idea, such as a faster palindrome method.

A faster palindrome method

There is a simpler method for the palindrome problem that uses almost no memory. A palindrome has a centre. An odd-length palindrome is centred on one letter, and an even-length palindrome is centred between two letters. So try every possible centre, and expand outwards while the letters on both sides match. The expansion stops at the first mismatch or at the edge of the string. The longest expansion is the answer.

This method takes O(n squared) time in the worst case, the same as the table. But it uses O(1) extra memory, because it only keeps two indexes and a best length. It is often the expected answer in interviews, because it is short and clear, and it shows you understand the structure of a palindrome. Use the table version when you are asked to show the DP, and the expansion version when memory is tight.

Common mistakes

Forgetting the base row and column. The edges must hold i and j. If they hold zero, the table says that an empty string is free to convert, and every answer comes out too small.

Taking the minimum of only two options. The recurrence has three neighbours. Leaving out the diagonal, the insertion or the deletion gives an answer that is too large on some inputs.

Confusing substring with subsequence. A palindromic substring must be one unbroken piece. A palindromic subsequence may skip letters. The palindrome loops in this lesson are for substrings.

Looping i forwards in the palindrome table. The cell pal[i][j] reads pal[i + 1][j - 1], which has not been filled if i goes up. The loop reads zeros and reports too few palindromes. The printed answer will be too small.

Reading the inside of a two-letter piece. For j - i equal to 1, the inside is pal[i + 1][j - 1], which is pal[i + 1][i]. That cell is never set to true, so a test without the j - i < 2 check says that aa is not a palindrome. The program then misses every palindrome of length 2.

Using min with a list and no include. The three-value min needs <algorithm>. Without it the compiler stops, with this message:

mn.cpp: In function ‘int main()’:
mn.cpp:6:16: error: no matching function for call to ‘min(<brace-enclosed initializer list>)’
    6 |     cout << min({a, b, c}) << "\n";
      |             ~~~^~~~~~~~~~~

The message says the call has a braced list that no min accepts. The fix is #include <algorithm> at the top of the file. Once it is there, the same line compiles, because the header declares the list form of min.

Overwriting a diagonal in the two-row version. If you write cur[j] over a value that the next cell needs as its diagonal, the next cell reads the new value. Save the old value in a variable before the write, or read from the separate row as the program in this lesson does.

Debugging walkthrough

Suppose the edit distance program prints 4 for sunday and saturday, and you expect 3. Work through it in order.

First, check the answer by hand. The known edits are insert a after s, insert t after that, and replace n with r. That is three steps, so 3 is correct.

Second, print the table, using the program in Part 3. Compare each row with your hand table, one row at a time. The first row should count up from 0 to 8, because saturday has eight letters, and the first column should count up from 0 to 6, because sunday has six.

Third, find the first wrong cell. Suppose the row for s and the column for sa is wrong. Look at its letters: s against sa. They do not match in the second position, so the cell is one plus the smallest neighbour. Check each neighbour against your table. The most common cause is a neighbour read from the wrong place, such as the cell above where the diagonal belongs.

Fourth, test the small cases. a and b should give 1. ab and ba should give 2. Empty input should give the length of the other string. Small tests show whether the base cases and the mismatch rule are right before you check the long words.

Variations and edge cases

Test these inputs before you rely on a solution.

• One empty word. The edit distance is the length of the other word, because every letter must be inserted or deleted.
• Two identical words. The distance is 0.
• Two words with no letters in common. The distance is the length of the longer word, because each position needs one replacement, and any extra letters need insertions.
• A single letter against a single letter. The distance is 0 if they match and 1 if they do not.
• A word that is one letter longer than the other, such as cat and cats. The distance is 1.
• For palindromes, a string of one letter, which is its own palindrome, and a string that is already a palindrome, which is its own longest palindrome.
• For palindromes, a string with two different palindromes of the same length, such as abc. Any one of them is a correct answer, and the program returns the length.

Edit distance changes when the costs change. If replacing a letter costs 2 instead of 1, the replacement term becomes 2 plus the diagonal, and insertions and deletions still cost 1. If you can swap two adjacent letters in one step, the table needs an extra case that looks two cells back. Each of these changes is a small edit to the recurrence, and the table structure stays the same.

Interview questions

"What is the time and space complexity of edit distance?" Answer: O(n times m) time and O(n times m) space for the full table, and O(m) space for the two-row version.

"Why is the answer always at most the length of the longer word?" Answer: you can replace each letter of the shorter word and insert the rest, so the cost never exceeds the longer length.

"How would you find the actual edits?" Answer: walk back from the bottom right cell, following the neighbour that gave the minimum. The move type tells you the operation.

"Why must the palindrome loop run backwards?" Answer: a piece reads the piece one step inside it, so the inner pieces must be ready first. Going down the start positions makes sure that holds.

"Can you check for a palindrome without a table?" Answer: yes. Expand around each centre while the letters match. This takes O(n squared) time and O(1) extra memory.

Practice

1. Easy. Find the edit distance between sunday and saturday. Predict the answer, then check it with the program. Hint: the answer is 3.

2. Easy. Find the edit distance between an empty string and abc, and between abc and abc. Explain both answers from the base cases.

3. Easy. Find the longest palindromic substring of racecar and of abcd. Say which piece is the answer in each.

4. Medium. Find the edit distance between intention and execution. Predict the answer, then check it with the program. Hint: the answer is 5.

5. Medium. Count the palindromic substrings of aaa. Every piece of aaa is a palindrome. List the pieces to be sure you have all of them.

6. Medium. Explain why the palindrome loop must go down over i, using the cell pal[i + 1][j - 1] as your example.

7. Medium. Change the edit distance so that a replacement costs 2 and insertions and deletions cost 1. Find the new answer for a and b.

8. Medium. Write the expansion-around-centre palindrome method for odd and even lengths. Explain why it uses O(1) extra space.

9. Hard. The minimum number of deletions needed to make a string a palindrome equals its length minus the length of its longest palindromic subsequence. The longest palindromic subsequence equals the LCS of the string and its reverse. Use this to find the number of deletions for abcde, and say which letters you would keep.

10. Hard. The longest common substring is the longest piece that appears in both strings as one unbroken block. Write the recurrence, using a cell that is 0 when letters differ. Find the answer for abcdxyz and xyzabcd.

What you now know

• Edit distance counts the fewest inserts, deletes and replaces that turn one string into another.
• Its table has a base row and a base column for the empty prefixes, and each mismatch costs one plus the smallest of three neighbours.
• A match copies the diagonal at no cost, which is why matching letters keep the table small.
• The full table can be walked back to recover the operations.
• Two rows are enough for the distance, because each cell reads only the row above and the cell to its left.
• The longest palindromic substring uses a table of true or false values, filled from the end of the string backwards.
• Expansion around each centre finds the same palindrome answer with almost no memory.
• The next part of the module is the assignment, which combines all five lessons in one program.