Edit Distance

1. Problem & Core Objective

Return the minimum number of operations to convert word1 into word2. Permitted operations: insert, delete, replace — each costing 1.

word1 = "horse", word2 = "ros"       →  3      rorse → rose → ros
word1 = "intention", word2 = "execution"  →  5

Constraints: 0 <= word1.length, word2.length <= 500 · lowercase

What's actually being tested: mapping each of the three operations onto a specific neighbouring cell, and getting the base cases right. It's the LCS template with a three-way min — the canonical Levenshtein distance.

2. First-Principles Thought Process

One index per string, again

dp[i][j] = the minimum operations to turn word1's first i characters into word2's first j.

Each operation is one neighbour

Considering the last characters of both prefixes:

They match. No operation needed — the problem reduces to the shorter prefixes:

dp[i][j] = dp[i-1][j-1]

They differ. One of three operations, each costing 1 plus a sub-problem:

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

The insert/delete mapping is the part people invert. Deleting from word1 shortens word1, so i decreases. Inserting into word1 adds a character matching word2[j-1], so j decreases while i stays — the inserted character isn't part of the original word1.

Worth deriving rather than memorising, because inverting them still produces a symmetric-looking table with the wrong answer on asymmetric inputs.

The base cases are not zero

Unlike LCS, the edges are not all zero:

dp[i][0] = i      delete all i characters
dp[0][j] = j      insert all j characters

Converting "abc" to "" costs 3, not 0. Forgetting these is the most common error — Java's zero-initialisation is wrong here.

Why a match doesn't need the min

When the characters match, dp[i-1][j-1] is always at least as good as any operation. Using them as-is costs nothing, and any alternative costs at least 1 more.

So the match branch takes the diagonal outright — the same exchange argument as in LCS.

3. Solution Paths

Approach 1 — Recursion

public int minDistance(String w1, String w2) {
    return dist(w1, w2, w1.length(), w2.length());
}

private int dist(String w1, String w2, int i, int j) {
    if (i == 0) return j;                            // insert all remaining
    if (j == 0) return i;                            // delete all remaining

    if (w1.charAt(i - 1) == w2.charAt(j - 1)) return dist(w1, w2, i - 1, j - 1);

    return 1 + Math.min(dist(w1, w2, i - 1, j),              // delete
               Math.min(dist(w1, w2, i, j - 1),              // insert
                        dist(w1, w2, i - 1, j - 1)));        // replace
}

• Time O(3^(m+n)) · Space O(m + n) stack

Counter-questions on this approach

⭐ "Why 3^(m+n) rather than 2^(m+n)?"

Three branches per mismatch instead of two. At m = n = 500 that's beyond naming — while only m × n = 250,000 distinct (i, j) states exist.

⭐ "Why does i == 0 return j rather than 0?"

Because word1's prefix is empty and word2's has j characters left — you must insert all j of them, costing j.

Returning 0 would claim the conversion is free, which is the single most common error in this problem. Converting "" to "abc" costs 3.

Approach 2 — 2-D tabulation

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

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

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (w1.charAt(i - 1) == w2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];                     // free
            else
                dp[i][j] = 1 + Math.min(dp[i - 1][j],            // delete
                           Math.min(dp[i][j - 1],                // insert
                                    dp[i - 1][j - 1]));          // replace
        }

    return dp[m][n];
}

Trace — word1 = "horse", word2 = "ros":

Answer dp[5][3] = 3 ✓ — replace h→r, delete r, delete e

• Time O(m · n) = 2.5 × 10^5 · Space O(m · n)

Counter-questions on this approach

⭐ "Map each operation to its cell, and justify the direction."

Delete removes word1[i-1], so word1's prefix shortens and word2's doesn't — dp[i-1][j].

Insert appends a character to word1 matching word2[j-1]. That character now accounts for word2[j-1], so word2's remaining prefix shortens while word1's original length is untouched — dp[i][j-1].

Replace changes word1[i-1] into word2[j-1], consuming one from each — dp[i-1][j-1].

Inverting insert and delete is the common error, and it produces a table that still looks plausible — symmetric inputs mask it. On "horse" → "ros" the asymmetry exposes it.

⭐ "Why is the diagonal taken outright on a match, without a min?"

Because matching characters cost nothing, and any operation costs at least 1. dp[i-1][j-1] therefore dominates every alternative.

Same exchange argument as LCS: using a free match is never worse than paying for an operation.

⭐ "Why do the base cases matter so much here when LCS's were zero?"

Because converting to or from an empty string isn't free. dp[i][0] = i says "delete all i characters", and dp[0][j] = j says "insert all j".

LCS's edges were genuinely 0 — an empty string shares nothing, at no cost. Here the cost is the length. Java's zero-initialised array gives the LCS answer, which is why this is the error people make.

"Is the answer symmetric in the two words?"

Yes — minDistance(a, b) == minDistance(b, a), because insert and delete are mirror operations and replace is symmetric. A useful sanity check, and it means you can always put the shorter word second to minimise the rolled row length.

Approach 3 — Rolled to one row (optimal)

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

    for (int j = 0; j <= n; j++) dp[j] = j;          // row 0: insert j characters

    for (int i = 1; i <= m; i++) {
        int prevDiagonal = dp[0];                     // dp[i-1][0]
        dp[0] = i;                                    // dp[i][0] = delete i characters

        for (int j = 1; j <= n; j++) {
            int temp = dp[j];                         // save dp[i-1][j] before overwriting
            if (w1.charAt(i - 1) == w2.charAt(j - 1))
                dp[j] = prevDiagonal;
            else
                dp[j] = 1 + Math.min(dp[j], Math.min(dp[j - 1], prevDiagonal));
            prevDiagonal = temp;                      // becomes the diagonal for j+1
        }
    }
    return dp[n];
}

• Time O(m · n) · Space O(n)

Counter-questions on this approach

⭐ "Explain prevDiagonal. Why is a single variable enough?"

The recurrence needs three cells: above (dp[j], still the previous row), left (dp[j-1], already this row), and the diagonal dp[i-1][j-1].

In one array, dp[j-1] has already been overwritten with the current row by the time we reach j, so the diagonal is lost. prevDiagonal holds it — it's set from dp[j] before the overwrite, so at the next iteration it's exactly dp[i-1][j-1].

One variable suffices because only the immediately-preceding column's old value is ever needed.

LCS used two full rows for the same reason; this is the leaner alternative, and worth showing since the trick is reusable.

⭐ "Why must dp[0] = i be set inside the outer loop?"

Because it's the base case for this row: converting word1's first i characters to the empty string costs i deletions.

And prevDiagonal must capture the old dp[0] — which is i−1 — before the overwrite, since it's the diagonal for j = 1.

Getting that order wrong makes the first column wrong, and every row after it.

"Which would you write in an interview?"

The 2-D table. It's clearer, it's only 1 MB at these constraints, and it's required if the edit script is ever wanted.

I'd mention the rolled version and write it if asked to reduce space.

"Could the distance overflow?"

No — it's bounded by max(m, n) = 500. The costs are all 1.

Comparison

4. Why the Optimal Wins

The recursion branches three ways over only m × n states.

The content is the operation-to-cell mapping: three operations, three neighbours, one min. Plus base cases that are lengths rather than zeros — the thing Java's default initialisation silently gets wrong.

The framing worth keeping:

Three operations, three neighbours: delete → above, insert → left, replace → diagonal. A match takes the diagonal free. And the edges are i and j, not 0 — converting to an empty string costs its length.

5. Java Prerequisites

The three-way min

dp[i][j] = 1 + Math.min(dp[i-1][j],                  // delete
           Math.min(dp[i][j-1],                      // insert
                    dp[i-1][j-1]));                  // replace

Math.min takes two arguments, so three candidates need nesting.

Base cases are lengths

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

Saving the diagonal when rolling

int temp = dp[j];        // dp[i-1][j], before it is overwritten
...
prevDiagonal = temp;     // becomes dp[i-1][j-1] for the next column

6. Interview Communication Guide

Clarifying questions: Do all three operations cost 1 (yes — weighted variants exist)? Is transposition allowed (no — that's Damerau-Levenshtein)? Can either string be empty (yes — and that's the base case)? Direction — word1 to word2 (yes, though the answer is symmetric)?

The pitch

"dp[i][j] is the minimum operations to turn word1's first i characters into word2's first j.

If the last characters match, no operation is needed — take the diagonal free. That's safe without a min, because matching costs nothing and any operation costs at least 1.

If they differ, each of the three operations maps to one neighbouring cell, and this is the part worth deriving rather than memorising:

Delete removes word1[i-1], so word1 shortens — dp[i-1][j]. Insert appends a character to word1 matching word2[j-1], so word2's remaining prefix shortens while word1's original length is untouched — dp[i][j-1]. Replace consumes one from each — dp[i-1][j-1].

So it's 1 + min of those three. Inverting insert and delete is the common error, and it produces a plausible-looking table that's wrong on asymmetric inputs.

The base cases are the other trap: they're not zero. dp[i][0] = i because converting to an empty string means deleting everything, and dp[0][j] = j because building from nothing means inserting everything. Java's zero-initialised array gives the LCS base cases, which are wrong here.

O(m·n) = 2.5 × 10^5 time, O(m·n) space — about 1 MB.

It rolls to one row with a single saved variable for the diagonal: dp[j] is still the previous row (above), dp[j-1] is already this row (left), and prevDiagonal holds the old dp[j-1] from before it was overwritten. LCS needed two full rows for the same reason; one variable is the leaner version.

I'd submit the 2-D table though — it's clearer and it's required if the actual edit script is wanted."

Edge cases to volunteer:

Name the two empty-string cases. They must return the length, not 0, and Java's default initialisation gives 0 — so a solution that forgets to seed the edges fails them while passing symmetric inputs.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual edit script, not just the count."

Keep the full table and walk back from dp[m][n], recording which neighbour was chosen. O(m·n) space, so the rolling is forfeited — the usual trade, and the reason I'd default to the 2-D form.

⭐ "What if the operations had different costs?"

Replace the 1 + with the specific cost per branch: dp[i-1][j] + deleteCost, and so on. The structure is unchanged, which shows the recurrence was never about the costs being equal.

With replace costing more than insert-plus-delete, the replace branch simply never wins — worth noticing as a sanity check.

"Allow transposition of adjacent characters."

Damerau-Levenshtein. Add a fourth branch reading dp[i-2][j-2] + 1 when word1[i-1] == word2[j-2] and word1[i-2] == word2[j-1]. Same shape, one more candidate.

"What if m and n were 10^4?"

O(m·n) = 10^8 — borderline, and the full table would be 400 MB. The rolled version fixes the memory. For similar strings, Ukkonen's algorithm runs in O(m · d) where d is the actual distance, which is much faster when the strings are close.

"Compute only whether the distance is at most k."

Then you only need a band of width 2k + 1 around the diagonal — cells outside it have distance greater than k regardless. O(m · k) time and space. That's the standard optimisation for approximate string matching.

"How does this relate to LCS?"

With only insert and delete allowed (no replace), the edit distance is m + n − 2·LCS(a,b). Replace is what breaks that identity, since it does in one operation what would otherwise take two.