Edit Distance: A Step-by-Step Dynamic Programming Interview Walkthrough

The Edit Distance dynamic programming question is one of the cleanest tests an interviewer has for whether you can reason about multi-dimensional state and justify transitions from first principles, rather than pattern-match to a memorized template. The technique you build here - defining state over prefixes and anchoring decisions at a boundary - is the same one that unlocks Longest Common Subsequence, Regular Expression Matching, and most other two-string DP problems you'll encounter.

It's also not a contrived puzzle. The algorithm, known as Levenshtein distance, runs inside spell checkers, Git diffs, DNA sequence alignment, and fuzzy search.

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2.

You may perform the following operations on word1:

• Insert a character

• Delete a character

• Replace a character

Example: word1 = "horse", word2 = "ros" → answer is 3.

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would affect my approach.

Inputs: two strings, word1 and word2.

Output: an integer - the minimum number of edits.

Details to clarify:

• Do all three operations have equal cost? If insert costs 1 but replace costs 2, the recurrence changes. Yes, assume costs are equal

• Can the strings be empty? What about very long? Yes, string can be empty and very long

• Do I need to return the actual sequence of edits, or just the count? Just the count

• Is the alphabet ASCII, Unicode, anything weird? Assume ASCII, nothing weird

2. Identify the Category of the Question

A few signals jump out:

• We're transforming one sequence into another.

• We're optimizing - finding a minimum.

• The operations are local (they act on one character at a time).

• The order of characters matters.

That combination - sequences, optimization, local choices - almost always points to dynamic programming. More specifically, this is a 2D DP over two strings, which is the same family as Longest Common Subsequence, Regular Expression Matching, and Distinct Subsequences. Once we notice that family, we have a template to lean on: the state is usually indexed by prefixes of the two inputs.

3. Brute Force Solution

As always, we start with the brute force solution. The most direct approach to the problem would be to try every possible sequence of edits and find the shortest one that produces word2.

That means at every step, we're at some intermediate string, and we can:

• Insert any of 26 characters at any position

• Delete any character

• Replace any character with any other

This branches enormously. From a single string, there are roughly O(n) deletes, O(26n) inserts, and O(26n) replaces - and then I do this again from each resulting string. Even for tiny inputs, the search tree explodes. Worse, I'd be exploring tons of redundant paths (insert 'a' then delete 'a' gets me back where I started).

So this is conceptually simple but completely infeasible. I'd mention it in an interview to show I understand the search space, then immediately move on. But the brute force does teach me one thing: the answer is the minimum over a set of choices. That structure is going to survive into the better solution.

4. Brainstorm More Solutions

Step 1: How would we solve this manually?

Let's think about how we would approach this problem if we were going to try and solve it manually. What would be the first move?

Truthfully, this is a little hard to reason about because "the first move" could happen anywhere in the string. I could insert at position 0, or position 5, or replace the third character. There's no natural anchor. So let's try putting some constraints around the search space.

Step 2: What if I commit to processing the strings in order?

Instead of "edit anywhere," what if I imagine walking through both strings left to right with two pointers, i in word1 and j in word2, and at each step I decide what to do? That feels more tractable because now I have a clear notion of "where I am."

Say I'm at position i in word1 and position j in word2. What are my options? Well, if word1[i] already equals word2[j], I just advance both pointers - no edits needed. If they don't match, I have to do something. Let's figure out exactly what that "something" could be.

Step 3: Enumerate the actual choices at a single position

If word1[i] != word2[j], I need to make word1 look like word2 at this spot. The problem gives me three operations, so let me think about what each one does to my pointers:

• Replace word1[i] with word2[j]. Now they match at this position. Both pointers advance. I've spent 1 edit.

• Delete word1[i]. That character is gone, so i advances but j stays put. I still need to match word2[j] against whatever comes next in word1. I've spent 1 edit.

• Insert word2[j] into word1 at position i. Now there's a match at this position, but I haven't consumed anything from the original word1 - so j advances and i stays put. I've spent 1 edit.

Three operations, three different effects on the pointers. And critically - these are the only three things I can do. The problem statement gave me exactly these operations, so any sequence of edits is some sequence of these pointer movements.

Step 4: This looks like a recursion

Now I can write a recurrence.

Let f(i, j) be the minimum edits to convert word1[i:] into word2[j:] (the suffixes starting at i and j).

if word1[i] == word2[j]: 
    f(i, j) = f(i+1, j+1) - no edits needed, so advance both.

Otherwise, take the cheapest of the three options:

• Replace: 1 + f(i+1, j+1)

• Delete: 1 + f(i+1, j)

• Insert: 1 + f(i, j+1)

That works. We should also note that we could write this same logic using prefixes rather than suffixes - dp[i][j] for the first i characters of word1 and first j of word2. The logic is identical, just mirrored: instead of asking "what happens at the start of the remaining strings?" I ask "what happens at the end of the prefixes I've built so far?"

Step 5: Base cases

Two clean ones, working with prefixes:

• f(0, j) = j - converting an empty string into a string of length j requires j insertions.

• f(i, 0) = i - converting a string of length i into the empty string requires i deletions.

Step 6: Optimize the recursive solution

When looking for optimizations in recursion, we should start by thinking about where we might be repeating work. If we implemented f(i, j) with plain recursion, we're recomputing the same subproblems exponentially.

Consider what happens at f(3, 4): it calls f(2, 3), f(2, 4), and f(3, 3).

Now look at f(2, 4) - it calls f(1, 3), f(1, 4), and f(2, 3). That f(2, 3) is the same subproblem the first call already computed.

As the recursion deepens, the same (i, j) pairs get recomputed over and over, and the call tree balloons toward O(3^(m+n)) in the worst case.

To optimize, let's try caching. The first time I see (i, j), I compute it and store it; every subsequent call returns the cached value in O(1). This is memoization, and it instantly drops the runtime to O(m × n) because each state is computed exactly once.

public int minDistance(String word1, String word2) {
    Integer[][] memo = 
        new Integer[word1.length() + 1][word2.length() + 1];
    return helper(word1, word2, 0, 0, memo);
}

private int helper(String w1, String w2, int i, int j, Integer[][] memo) {
    if (i == w1.length()) 
        return w2.length() - j;  // insert what's left of w2
    if (j == w2.length()) 
        return w1.length() - i;  // delete what's left of w1
    if (memo[i][j] != null) 
        return memo[i][j]; // return cached result

    int result;
    if (w1.charAt(i) == w2.charAt(j)) {
        result = helper(w1, w2, i + 1, j + 1, memo);
    } else {
        int replace = helper(w1, w2, i + 1, j + 1, memo);
        int delete  = helper(w1, w2, i + 1, j, memo);
        int insert  = helper(w1, w2, i, j + 1, memo);
        result = 1 + Math.min(replace, Math.min(delete, insert));
    }
    return memo[i][j] = result;
}

Step 7: From memoization to bottom-up 2D DP

Memoization helps, but recursion still has two annoyances. First, recursion incurs a real cost - function call overhead, and a stack depth proportional to m + n that can blow up on long inputs. Second, the order in which subproblems get computed depends on the recursion's traversal, which makes the code harder to reason about than it needs to be.

If we were to build a dependency graph of every state, we would see that every (i, j) depends on three others: (i-1, j-1), (i-1, j), and (i, j-1). Those are all states with smaller indices. That means we can flip the computation around: instead of starting from (0, 0) and recursing down toward the base cases, we can start from the base cases and iterate up. We first fill in row 0 and column 0 with their known values, then fill in each cell by reading the three neighbors we've already computed.

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1],
                    Math.min(dp[i - 1][j], dp[i][j - 1])
                );
            }
        }
    }
    return dp[m][n];
}

We end up with the same O(m × n) time and space, but no recursion stack, no function call overhead, and the order of computation is explicit.

Step 8: From 2D DP to rolling rows

To optimize even further, let's think about whether we really need the entire dp table. If we look closely at the recurrence, we see that dp[i][j] depends only on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1]. Every dependency is either in the current row or the previous row. Rows older than that are dead weight - once I've finished row i, I never look at row i-2 again.

That means I don't need a full 2D table. I only need two rows at a time: the previous one and the one I'm currently building. After finishing each row, I overwrite the "previous" row with what I just built and move on. That drops our memory requirements from O(m × n) to O(n).

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    // Always iterate over the longer string, store the shorter — O(min(m, n)) space
    if (n > m) return minDistance(word2, word1);

    int[] prev = new int[n + 1];
    int[] curr = new int[n + 1];
    for (int j = 0; j <= n; j++) prev[j] = j;

    for (int i = 1; i <= m; i++) {
        curr[0] = i;
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                curr[j] = prev[j - 1];
            } else {
                curr[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], curr[j - 1]));
            }
        }
        int[] temp = prev; prev = curr; curr = temp;  // swap
    }
    return prev[n];
}

You can push this further to a single 1D array by overwriting in place, but it requires saving the value of dp[j-1] from the previous row before you clobber it (since the new dp[j-1] would otherwise overwrite it before the next cell needs it). I'd only reach for that version if explicitly asked - the two-row version is clearer and just as fast, and clarity matters when you're explaining your code under pressure.

This progression - recursion → memoization → 2D DP → rolling rows - isn't four separate solutions. It's one solution being refined. Each step removes a specific inefficiency: memoization removes redundant computation, bottom-up removes the stack, and rolling rows removes the unused rows of the table. Showing that progression in an interview demonstrates that you understand why the optimizations work, not just that they exist. It's a pattern you can count on in DP problems.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Brute-force search over edits	Exponential	Exponential	Never - but worth mentioning to frame the problem
Recursion + memoization	O(m × n)	O(m × n)	Easiest to write if I'm short on time and the recurrence is fresh
Bottom-up 2D DP	O(m × n)	O(m × n)	My default interview answer - clean and easy to walk through
Bottom-up with rolling rows	O(m × n)	O(min(m, n))	If asked to optimize space, or if the strings are huge

6. Pseudocode

m = length of word1
n = length of word2
dp = 2D array of size (m + 1) x (n + 1)

# Base cases: converting to/from empty string
for i from 0 to m: dp[i][0] = i
for j from 0 to n: dp[0][j] = j

for i from 1 to m:
    for j from 1 to n:
        if word1[i - 1] == word2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = 1 + min(
                dp[i - 1][j],     # delete from word1
                dp[i][j - 1],     # insert into word1
                dp[i - 1][j - 1]  # replace
            )

return dp[m][n]

7. Edge Cases

Things I'd verify before claiming I'm done:

• Both strings empty → dp[0][0] = 0. ✓

• One string empty → handled by the base case row/column. ✓

• Identical strings → diagonal stays at zero, answer is 0. ✓

• Completely different strings of equal length → answer equals the length (all replaces). ✓

• Strings of very different lengths → the difference shows up as a sequence of inserts or deletes.

The base case initialization handles all of these without special-casing.

8. Full Code

public class EditDistance {

    public static int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        // Base cases
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i - 1][j],
                        Math.min(dp[i][j - 1], dp[i - 1][j - 1])
                    );
                }
            }
        }

        return dp[m][n];
    }
}

9. Test the Code

System.out.println(minDistance("horse", "ros"));            // 3
System.out.println(minDistance("intention", "execution"));  // 5
System.out.println(minDistance("abc", "abc"));              // 0
System.out.println(minDistance("", "abc"));                 // 3
System.out.println(minDistance("abc", ""));                 // 3

These hit the meaningful cases: a real transformation, a longer transformation, equality, and both empty-string directions.

10. Key Lessons

• When a search space feels unbounded (like "try every possible edit" in step 1 of our solution), look for an ordering or anchor that forces every choice to happen at one well-defined place. Here, anchoring at the ends of both prefixes turned an unbounded search into a 2D table.

• Two-string DP problems almost always have state dp[i][j] over prefixes of the two strings. Once you know that, the only real work is figuring out the transition.

• Base cases aren't an afterthought. For grid DP, they define the edges of your table, and getting them right is half the battle.

• If the interviewer pushes on space, point out that each row only depends on the previous row - that's the door to the O(min(m, n)) optimization.

The thing that makes Edit Distance click isn't the table. It's the realization that you only ever need to reason about what happens at the boundary of two prefixes. Once you see that, every other 2D string DP problem starts to look familiar.

Good Luck and Happy Coding!