Skip to main content

55. Edit Distance

mediumAsked at Salesforce

Compute the minimum number of insertions, deletions, or substitutions to transform one string into another. Salesforce uses this as the canonical 2D DP problem with three-way transitions.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses Levenshtein in their fuzzy-search for Contact lookup.
  • Blind (2025-11)— Common at Salesforce L5+ onsites.

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 (remove r); rose -> ros (remove e).

Example 2

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

Approaches

1. Recursive without memo

Try all three operations at each diff position.

Time
O(3^(m+n))
Space
O(m+n)
function minDistance(word1, word2) {
  function dp(i, j) {
    if (i === 0) return j;
    if (j === 0) return i;
    if (word1[i-1] === word2[j-1]) return dp(i-1, j-1);
    return 1 + Math.min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1));
  }
  return dp(word1.length, word2.length);
}

Tradeoff: Exponential without memo. Salesforce expects DP.

2. 2D DP table

dp[i][j] = min ops to convert word1[0..i] to word2[0..j]. Transitions: equal → dp[i-1][j-1]; else 1 + min(delete, insert, replace).

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));
  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: O(m*n) time and space. Compressible to O(n) with a rolling row. Salesforce's expected answer.

Salesforce-specific tips

Salesforce uses Levenshtein in their Contact fuzzy-search (typo-tolerant name lookup). They grade on whether you can articulate the three transitions (insert, delete, replace) and the base cases (i=0 → j, j=0 → i). Bonus signal: mention this generalizes to weighted edits (custom costs for insert/delete/replace) — useful for spell-checkers.

Common mistakes

  • Off-by-one on the dp indices (dp[i][j] corresponds to word1[0..i-1] vs word2[0..j-1]).
  • Forgetting the base cases — dp[0][j] = j (insert j chars from empty), dp[i][0] = i (delete i chars).
  • Confusing the three transitions — delete is dp[i-1][j], insert is dp[i][j-1], replace is dp[i-1][j-1].

Follow-up questions

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

  • One Edit Distance (LC 161) — boolean version.
  • Delete Operation for Two Strings (LC 583) — only delete allowed.
  • Reconstruct the actual sequence of operations.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What do delete, insert, replace correspond to in the DP?

Delete (from word1): dp[i-1][j]. Insert (into word1): dp[i][j-1]. Replace: dp[i-1][j-1]. The 1 + accounts for the operation itself.

Can I reduce to O(n) space?

Yes — only the previous row is needed. Roll forward with two arrays or one array + temp variable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →