54. Edit Distance

Q: Why three operations and not four?

The 'no-op' is implicit when characters match. The four standard ops sometimes include 'transpose' (Damerau-Levenshtein), but classic edit distance uses just three.

Q: Why O(n) space possible?

Each row depends only on the row above and the current row. Two rolling arrays of length n suffice — and you can collapse to one with a temp variable.

mediumAsked at Plaid

Find the minimum operations to convert one string into another (insert, delete, replace). Plaid asks this because fuzzy merchant matching uses edit distance to collapse variants like 'STARBUCKS #234' and 'Starbucks #234A' into one canonical merchant.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid SWE III onsite — framed as merchant fuzzy matching.
Blind (2026)— Plaid backend platform OA.

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

Example 2

Input

word1 = "intention", word2 = "execution"

Output

Approaches

1. Recursive without memo

ed(i, j) = ed(i-1, j-1) if word1[i] == word2[j]; else 1 + min(insert, delete, replace).

Time: O(3^(m+n))
Space: O(m+n)

// Exponential without memo. Mention as starting point.

Tradeoff: TLE.

2. 2D DP table

dp[i][j] = edit distance from word1[0..i] to word2[0..j]. Build bottom-up.

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: O(m*n) time and space. Can be reduced to O(n) space with rolling rows.

Plaid-specific tips

Plaid loves this because it's the building block for fuzzy merchant matching. Bonus signal: name the three operations and explain why each maps to a specific table cell — delete = dp[i-1][j], insert = dp[i][j-1], replace = dp[i-1][j-1]. Discuss the rolling-row optimization that reduces to O(n) space.

Common mistakes

Confusing 'insert' and 'delete' on the recurrence — they map to symmetric cells.
Forgetting the base case (empty string costs equal the other string's length).
Off-by-one between dp indices and word indices (dp[i] corresponds to word[i-1]).

Follow-up questions

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

Reduce to O(n) space.
Print one of the optimal edit scripts.
Weighted edit distance — different cost per operation.

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 three operations and not four?

The 'no-op' is implicit when characters match. The four standard ops sometimes include 'transpose' (Damerau-Levenshtein), but classic edit distance uses just three.

Why O(n) space possible?

Each row depends only on the row above and the current row. Two rolling arrays of length n suffice — and you can collapse to one with a temp variable.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →