Skip to main content

72. Edit Distance

hardAsked at Google

Given two strings, return the minimum number of insertions, deletions, and substitutions to transform one into the other. Google asks this to test whether you can set up a 2D DP recurrence cleanly and articulate why each character pair has exactly four sub-choices.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4/L5 onsite reports cite this as the DP-heavy round.
  • Blind (2025-11)— Recurring Google interview question for senior IC roles.

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word: Insert a character, Delete a character, Replace a character.

Constraints

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Examples

Example 1

Input
word1 = "horse", word2 = "ros"
Output
3

Explanation: horse -> rorse (replace h with r), rorse -> rose (delete r), rose -> ros (delete e).

Example 2

Input
word1 = "intention", word2 = "execution"
Output
5

Approaches

1. Recursion with memoization

Define solve(i, j) = edit distance for word1[0..i] and word2[0..j]. If chars match, recurse on (i-1, j-1). Else min of insert/delete/replace + 1.

Time
O(m * n)
Space
O(m * n)
function minDistanceMemo(word1, word2) {
  const memo = new Map();
  function solve(i, j) {
    if (i === 0) return j;
    if (j === 0) return i;
    const key = i + ',' + j;
    if (memo.has(key)) return memo.get(key);
    let result;
    if (word1[i - 1] === word2[j - 1]) {
      result = solve(i - 1, j - 1);
    } else {
      result = 1 + Math.min(solve(i - 1, j), solve(i, j - 1), solve(i - 1, j - 1));
    }
    memo.set(key, result);
    return result;
  }
  return solve(word1.length, word2.length);
}

Tradeoff: Same complexity as bottom-up but uses recursion stack. Good for explaining the subproblem structure first.

2. Bottom-up 2D DP (optimal whiteboard answer)

dp[i][j] = edit distance for word1[0..i] and word2[0..j]. Base cases on the empty prefixes; recurrence as above.

Time
O(m * n)
Space
O(m * n)
function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  return dp[m][n];
}

Tradeoff: Bottom-up avoids the recursion stack. The recurrence makes the three operations visible at the same call site: insert = dp[i][j-1] + 1, delete = dp[i-1][j] + 1, replace = dp[i-1][j-1] + 1.

Google-specific tips

Google interviewers want you to label the three operations on the recurrence: which dp[..][..] corresponds to insert, delete, replace. Articulating the mapping explicitly is what separates 'I memorized the recurrence' from 'I derived it.' Bonus: mention that the space can be reduced to O(n) by keeping only the previous row.

Common mistakes

  • Off-by-one with the dp indices (dp[i][j] uses word1[i-1] and word2[j-1]).
  • Confusing which operation corresponds to which dp transition.
  • Forgetting the base cases — dp[i][0] = i (delete all of word1) and dp[0][j] = j (insert all of word2).

Follow-up questions

An interviewer at Google may pivot to one of these next:

  • Reduce space to O(min(m, n)) using one row.
  • Reconstruct the actual sequence of operations, not just the count.
  • Add a 'swap adjacent characters' operation (Damerau-Levenshtein).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why exactly three operations and not four?

Insert, delete, replace cover all single-character transformations. Substitution from one specific char to another is the same as 'replace' — the cost is the same regardless of source/target chars.

Can it be done in O(min(m, n)) space?

Yes. At each iteration, dp[i][j] only depends on the current and previous row. Track two rows, alternating. Most interviewers don't require this unless they specifically ask.

Practice these live with InterviewChamp.AI

Drill Edit Distance and other Google interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →