Frontend Prep

Appearance

Edit Distance ​

Problem Statement ​

Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. Three operations are allowed:

  • Insert a character.
  • Delete a character.
  • Replace a character.

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
  horse → rorse (replace 'h' with 'r')
  rorse → rose  (delete 'r')
  rose  → ros   (delete 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
  intention → inention (remove 't')
  inention  → enention (replace 'i' with 'e')
  enention  → exention (replace 'n' with 'x')
  exention  → exection (replace 'n' with 'c')
  exection  → execution (insert 'u')

Constraints:

  • 0 <= word1.length, word2.length <= 500.

Difficulty: Hard (treated as Medium-ish for prep) LC: 72 Round: Technical R2

Pattern Recognition ​

  • What is the input structure? Two strings.
  • What are we optimizing? Minimum number of single-character edits.
  • What pattern does this fit? 2D DP — the Levenshtein distance algorithm.
  • Why does this pattern fit? At position (i, j), you either have matching characters (no op) or choose among three operations (insert, delete, replace), each recursing into a smaller subproblem. Classic overlapping subproblems.

Approach ​

Brute Force — Recursion ​

For each character mismatch, try all three operations and recurse.

Time: Exponential (3^(n+m)). Space: O(n + m) recursion depth. Why insufficient: Repeated subproblems make this infeasible past n = 10.

Optimal — 2D DP ​

Key Insight: dp[i][j] = min edits to convert word1[0..i-1] into word2[0..j-1]. Either the current characters match (no cost, inherit diagonal), or we pay 1 edit and move to one of three predecessor states.

Transitions:

  • If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (no op).
  • Else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
    • dp[i-1][j-1] + 1 — replace word1[i-1] with word2[j-1].
    • dp[i-1][j] + 1 — delete word1[i-1].
    • dp[i][j-1] + 1 — insert word2[j-1] into word1.

Base: dp[i][0] = i (delete i chars), dp[0][j] = j (insert j chars).

Time: O(n * m). Space: O(n * m), reducible to O(m).

Walkthrough ​

Trace on word1 = "horse", word2 = "ros":

n = 5, m = 3. Initial base row/column:

""ros
""0123
h1
o2
r3
s4
e5

Fill cell-by-cell:

  • (h, r): h != r. min(0, 1, 1) + 1 = 1. Set dp[1][1] = 1.
  • (h, o): h != o. min(1, 1, 2) + 1 = 2. dp[1][2] = 2.
  • (h, s): h != s. min(2, 2, 3) + 1 = 3. dp[1][3] = 3.
  • (o, r): o != r. min(1, 2, 2) + 1 = 2. dp[2][1] = 2.
  • (o, o): o == o. dp[2][2] = dp[1][1] = 1.
  • (o, s): o != s. min(2, 1, 3) + 1 = 2. dp[2][3] = 2.
  • (r, r): r == r. dp[3][1] = dp[2][0] = 2.
  • (r, o): r != o. min(2, 1, 3) + 1 = 2. dp[3][2] = 2.
  • (r, s): r != s. min(1, 2, 2) + 1 = 2. dp[3][3] = 2.
  • (s, r): s != r. min(3, 2, 4) + 1 = 3. dp[4][1] = 3.
  • (s, o): s != o. min(2, 2, 3) + 1 = 3. dp[4][2] = 3.
  • (s, s): s == s. dp[4][3] = dp[3][2] = 2.
  • (e, r): e != r. min(4, 3, 5) + 1 = 4. dp[5][1] = 4.
  • (e, o): e != o. min(3, 3, 4) + 1 = 4. dp[5][2] = 4.
  • (e, s): e != s. min(3, 2, 4) + 1 = 3. dp[5][3] = 3.

Answer: dp[5][3] = 3.

Implementation ​

typescript
function minDistance(word1: string, word2: string): number {
    const n = word1.length, m = word2.length;
    const dp: number[][] = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

    // Base: converting empty string to word2[0..j-1] requires j inserts.
    for (let j = 0; j <= m; j++) dp[0][j] = j;
    // Base: converting word1[0..i-1] to empty requires i deletes.
    for (let i = 0; i <= n; i++) dp[i][0] = i;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // no op
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1], // replace
                    dp[i - 1][j],     // delete
                    dp[i][j - 1],     // insert
                );
            }
        }
    }
    return dp[n][m];
}
cpp
#include <string>
#include <vector>
#include <algorithm>

int minDistance(std::string word1, std::string word2) {
    int n = word1.size(), m = word2.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + std::min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
            }
        }
    }
    return dp[n][m];
}

Watch out:

  1. Mixing up insert vs delete transitions. Delete = dp[i-1][j] + 1 (drop from word1). Insert = dp[i][j-1] + 1 (match current word1 against word2 with one extra char inserted).
  2. Forgetting base cases. Without dp[0][j] = j and dp[i][0] = i, you get wrong answers for "empty to string" transitions.
  3. Incrementing by 2 on replace. Replace is one operation, not two (it's not "delete + insert").

Complexity Analysis ​

TimeSpace
Brute ForceO(3^(n+m))O(n+m)
2D DPO(n * m)O(n * m)
Space-OptimizedO(n * m)O(m)

Bottleneck: Every cell of the n x m table depends on three predecessors; all must be computed.

Edge Cases ​

  1. Empty word1 — answer is word2.length (all inserts).
  2. Empty word2 — answer is word1.length (all deletes).
  3. Identical strings — answer is 0.
  4. Disjoint alphabets — answer is max(n, m) (all replaces plus the remainder).
  5. One is a subsequence of the other — answer is |n - m| if they differ only in extras.
  • LC 1143 — Longest Common Subsequence — Same 2D DP skeleton with simpler transitions.
  • LC 583 — Delete Operation for Two Strings — Only delete allowed; min deletes = n + m - 2 * LCS.
  • LC 161 — One Edit Distance — The "is edit distance exactly 1?" variant. O(n).
  • LC 712 — Minimum ASCII Delete Sum — Same DP shape, different cost function.

Interview Strategy Notes ​

Classic hard DP. Expect 25-35 minutes in Technical R2. The interviewer will often ask for the space optimization and may push on "can you print the actual edit operations?" — which requires keeping a backpointer matrix. Practice both.

What is Expected at Each Level ​

Junior: Writes recursive/memoized solution. Gets the three operations right with help. May struggle with base cases.

Mid-level: Writes bottom-up DP cleanly. Handles all three operations. Explains transitions precisely.

Senior: Implements space-optimized O(m). Derives the operation sequence via backpointer trace. Mentions the Hirschberg algorithm for O(min(n, m)) space with the actual alignment.

Frontend interview preparation reference.