54. Edit Distance

Q: Which operation does dp[i-1][j-1] correspond to?

Replace. If we did 'replace,' both string pointers advance, hence i-1 and j-1.

Q: Can you use only O(min(n,m)) space?

Yes — rolling 1D array. Save the diagonal before overwriting dp[i][j-1].

mediumAsked at Datadog

Compute the minimum number of insert/delete/replace operations to convert one string into another (Levenshtein distance). Datadog asks this for the classic 2D DP — same recurrence they use when diffing two metric-name versions during schema migration.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog onsite DP staple.
LeetCode Discuss (2025-09)— Datadog tagged.

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

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

Time: O(3^max(n, m))
Space: O(max(n, m))

function minDistance(w1, w2) {
  function f(i, j) {
    if (i < 0) return j + 1;
    if (j < 0) return i + 1;
    if (w1[i] === w2[j]) return f(i - 1, j - 1);
    return 1 + Math.min(f(i, j - 1), f(i - 1, j), f(i - 1, j - 1));
  }
  return f(w1.length - 1, w2.length - 1);
}

Tradeoff: Exponential — overlapping subproblems. Datadog requires memoization.

2. 2D DP table (optimal)

dp[i][j] = edit distance for w1[0..i] vs w2[0..j]. If chars match, copy diagonal; else 1 + min(left, up, diag).

Time: O(n * m)
Space: O(n * m)

function minDistance(w1, w2) {
  const n = w1.length, m = w2.length;
  const dp = Array.from({length: n + 1}, () => new Array(m + 1).fill(0));
  for (let i = 0; i <= n; i++) dp[i][0] = i;
  for (let j = 0; j <= m; j++) dp[0][j] = j;
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      if (w1[i - 1] === w2[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[n][m];
}

Tradeoff: Quadratic time and space. Datadog accepts O(n*m); rolling-array can reduce to O(min(n, m)).

Datadog-specific tips

Datadog grades on the recurrence: same char = no op; mismatch = 1 + min(insert, delete, replace). Articulate which DP direction corresponds to which operation BEFORE coding (dp[i-1][j] = delete from w1; dp[i][j-1] = insert into w1; dp[i-1][j-1] = replace).

Common mistakes

Initializing dp[0][0] to non-zero — it's 0 (empty to empty needs 0 ops).
Forgetting to handle empty-string base cases — dp[i][0] = i, dp[0][j] = j.
Using w1[i] instead of w1[i-1] — off-by-one between DP indices and string indices.

Follow-up questions

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

Reconstruct the actual edit sequence — backtrack through dp.
One Edit Distance (LC 161) — special case k=1.
Datadog-style: compute diff between two versions of a metric schema.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Which operation does dp[i-1][j-1] correspond to?

Replace. If we did 'replace,' both string pointers advance, hence i-1 and j-1.

Can you use only O(min(n,m)) space?

Yes — rolling 1D array. Save the diagonal before overwriting dp[i][j-1].

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →