Skip to main content

54. Edit Distance

hardAsked at Workday

Compute the minimum number of operations (insert, delete, replace) to convert one string to another. Workday uses this for string-DP fluency — same shape as detecting close-match HRIS records during deduplication.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday HRIS integration team — direct dedup analogy.

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

Example 2

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

Approaches

1. Recursion + memo

f(i, j) = 0 if i or j is 0 (return the non-zero one). Else if equal chars, f(i-1, j-1). Else 1 + min(insert, delete, replace).

Time
O(m*n)
Space
O(m*n) memo)
// classic memoized recursion — same complexity as iterative DP

Tradeoff: Same complexity; stack depth is the only downside.

2. Bottom-up 2D DP

dp[i][j] = min ops to convert word1[..i] to word2[..j]. Base: dp[i][0]=i, dp[0][j]=j.

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: Standard Levenshtein distance. O(m*n) time and space; can be reduced to O(min(m, n)) space with rolling rows.

Workday-specific tips

Workday wants you to explicitly map the three operations to the three recurrences: dp[i-1][j] = delete from word1, dp[i][j-1] = insert into word1, dp[i-1][j-1] = replace. Articulate this mapping before writing.

Common mistakes

  • Confusing which dp value maps to which operation.
  • Off-by-one indexing — word1[i-1] vs word1[i].
  • Missing the base case dp[i][0] = i.

Follow-up questions

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

  • One Edit Distance (LC 161).
  • Optimize to O(min(m, n)) space with rolling rows.
  • What if operation costs differ?

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 dp[i-1][j-1] for replace?

Replace consumes one character from each string. The remaining subproblem is converting word1[..i-1] to word2[..j-1].

Same as Levenshtein?

Yes — Edit Distance is Levenshtein with insert, delete, replace all cost 1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →