72. Edit Distance

hardAsked at Juniper Networks

Compute the minimum edit operations (insert, delete, replace) to transform one string into another using 2D DP. Juniper applies edit distance in network configuration management — computing how far a running device configuration has drifted from a desired state, or how similar two YANG model paths are, uses this exact algorithm.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

Glassdoor (2025-Q4)— Cited in Juniper senior SWE and architect onsite reports as a classic 2D DP hard problem.
Blind (2025-10)— Juniper interview prep threads list Edit Distance as a must-know hard DP problem for software and platform engineering roles.

Problem

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

Constraints

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

Examples

Example 1

Input

word1 = "horse", word2 = "ros"

Output

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

Example 2

Input

word1 = "intention", word2 = "execution"

Output

Explanation: 5 operations to transform intention into execution.

Approaches

1. Bottom-up 2D DP

dp[i][j] = edit distance between word1[0..i-1] and word2[0..j-1]. Base cases: dp[i][0] = i (delete i chars), dp[0][j] = j (insert j chars). Recurrence: if chars match, dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

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 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
  );
  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]; // no operation needed
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete from word1
          dp[i][j - 1],     // insert into word1
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }
  return dp[m][n];
}

Tradeoff: O(m*n) time and space. The standard 2D DP solution. Draw the table — Juniper interviewers often ask you to fill in a small example manually.

2. Space-optimized — two 1D arrays

Each row of the DP table only depends on the current and previous rows. Use two 1D arrays (prev and curr) to reduce space to O(n).

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

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

Tradeoff: O(m*n) time, O(n) space. The space optimization follows naturally once you note that dp[i][j] only reads from dp[i-1][*] and dp[i][j-1].

Juniper Networks-specific tips

Name Levenshtein distance — Juniper interviewers value knowing the formal name. Walk through the three operations and their DP mapping: delete from word1 = dp[i-1][j] + 1, insert into word1 (equivalent to delete from word2) = dp[i][j-1] + 1, replace = dp[i-1][j-1] + 1. Filling in a 3x3 table on the whiteboard is the fastest way to build mutual confidence in the solution's correctness. Connect to Junos: 'Computing the diff between a running config snapshot and a desired-state YANG model uses edit distance as the core similarity measure.'

Common mistakes

Confusing the three operations in the recurrence — draw the DP table and label which cell each operation corresponds to.
Not initializing the first row and column — dp[i][0] = i (delete i chars from word1), dp[0][j] = j (insert j chars).
Using 0-indexed vs 1-indexed word access inconsistently — dp[i][j] represents word1[0..i-1], so access is word1[i-1] and word2[j-1].
Not recognizing the match case — when characters are equal, dp[i][j] = dp[i-1][j-1] with no +1.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

Longest Common Subsequence (LC 1143) — edit distance without the replace operation.
Delete Operation for Two Strings (LC 583) — only insert/delete allowed.
How would you compute configuration drift between two Junos device snapshots using edit distance on config lines?

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 the three DP predecessors represent?

dp[i-1][j] = delete word1[i-1] (reduce word1 by one char); dp[i][j-1] = insert word2[j-1] into word1 (reduce word2 by one char); dp[i-1][j-1] = replace word1[i-1] with word2[j-1].

Why is this called the Levenshtein distance?

After Vladimir Levenshtein who introduced the metric in 1965. It measures the minimum number of single-character edits (insertions, deletions, substitutions) between two strings.

What is the space complexity of the optimized version?

O(n) where n = word2.length. We keep only two rows of the DP table at a time. If m < n, swap word1 and word2 to ensure the smaller dimension indexes columns.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →