Edit Distance

🎯

Edit Distance

hardMIXEDGoogleAmazonMicrosoft

Imagine you are building a spell checker or a DNA sequence analyzer that needs to find how similar two strings are by counting the minimum edits needed to convert one string into another.

💡 Edit Distance is a classic string transformation problem that beginners find challenging because it requires considering multiple operations (insert, delete, replace) and their combinations. Understanding brute force recursion helps grasp the problem's complexity before moving to dynamic programming.

📋

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following operations permitted on a word: 1. Insert a character 2. Delete a character 3. Replace a character Input: Two strings word1 and word2 Output: Integer representing minimum edit distance

1 ≤ word1.length, word2.length ≤ 5000word1 and word2 consist of lowercase English letters

💡

Example

Input"word1 = \"horse\", word2 = \"ros\""

Output3

horse -> rorse (replace 'h' with 'r') -> rose (remove 'r') -> ros (remove 'e')

Input"word1 = \"intention\", word2 = \"execution\""

Output5

intention -> inention (remove 't') -> enention (replace 'i' with 'e') -> exention (replace 'n' with 'x') -> exection (replace 'n' with 'c') -> execution (insert 'u')

• Both strings empty → 0
• One string empty, other non-empty → length of non-empty string
• Strings are identical → 0
• Strings differ by one character → 1

⚠️

Common Mistakes

Not handling empty string base cases correctly

Incorrect results or index errors

✅ Explicitly initialize DP base cases for empty substrings

Confusing indices i and j or off-by-one errors

Wrong answers or runtime exceptions

✅ Carefully define dp dimensions and consistently use indices

Forgetting to check character equality before operations

Unnecessary operations increase edit distance

✅ Add condition to skip operations if characters match

Using recursion without memoization on large inputs

Time limit exceeded or stack overflow

✅ Add memoization or switch to bottom-up DP

Incorrectly updating DP table order in bottom-up approach

Using uninitialized values leads to wrong answers

✅ Fill DP table from bottom-right to top-left

🧠

Brute Force (Pure Recursion)

💡 This approach exists to build intuition by exploring all possible operations recursively. It is slow but helps understand the problem's exponential nature and why optimization is needed.

Intuition

Try all three operations (insert, delete, replace) at each step and recursively compute the minimum edits needed for the remaining substrings.

Algorithm

1. If either string is empty, return the length of the other string (all insertions or deletions).
2. If last characters match, recurse on the remaining substrings without any operation.
3. Otherwise, recursively compute the cost of insert, delete, and replace operations and take the minimum plus one.
4. Return the minimum edit distance computed.

💡 The recursion tree grows exponentially because each mismatch branches into three recursive calls, making it hard to track without memoization.

</>

Code

def minDistance(word1: str, word2: str) -> int:
    def dfs(i, j):
        if i == len(word1):
            return len(word2) - j
        if j == len(word2):
            return len(word1) - i
        if word1[i] == word2[j]:
            return dfs(i + 1, j + 1)
        insert = 1 + dfs(i, j + 1)
        delete = 1 + dfs(i + 1, j)
        replace = 1 + dfs(i + 1, j + 1)
        return min(insert, delete, replace)

    return dfs(0, 0)

# Example usage:
if __name__ == '__main__':
    print(minDistance("horse", "ros"))  # Output: 3

Line Notes

def dfs(i, j):Defines a helper function to compute edit distance starting at indices i and j

if i == len(word1):If word1 is exhausted, remaining characters in word2 must be inserted

if j == len(word2):If word2 is exhausted, remaining characters in word1 must be deleted

if word1[i] == word2[j]:If characters match, no operation needed, move both pointers

insert = 1 + dfs(i, j + 1)Try inserting a character into word1 to match word2[j]

delete = 1 + dfs(i + 1, j)Try deleting a character from word1

replace = 1 + dfs(i + 1, j + 1)Try replacing word1[i] with word2[j]

return min(insert, delete, replace)Choose the operation with minimum cost

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        return dfs(word1, word2, 0, 0);
    }

    private static int dfs(String w1, String w2, int i, int j) {
        if (i == w1.length()) return w2.length() - j;
        if (j == w2.length()) return w1.length() - i;
        if (w1.charAt(i) == w2.charAt(j)) {
            return dfs(w1, w2, i + 1, j + 1);
        }
        int insert = 1 + dfs(w1, w2, i, j + 1);
        int delete = 1 + dfs(w1, w2, i + 1, j);
        int replace = 1 + dfs(w1, w2, i + 1, j + 1);
        return Math.min(insert, Math.min(delete, replace));
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // Output: 3
    }
}

Line Notes

public static int dfs(String w1, String w2, int i, int j)Recursive helper to compute edit distance from indices i and j

if (i == w1.length())If word1 is exhausted, insert remaining chars of word2

if (j == w2.length())If word2 is exhausted, delete remaining chars of word1

if (w1.charAt(i) == w2.charAt(j))If chars match, move both pointers without cost

int insert = 1 + dfs(w1, w2, i, j + 1);Try insertion operation

int delete = 1 + dfs(w1, w2, i + 1, j);Try deletion operation

int replace = 1 + dfs(w1, w2, i + 1, j + 1);Try replacement operation

return Math.min(insert, Math.min(delete, replace));Return minimum cost among operations

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dfs(const string& w1, const string& w2, int i, int j) {
    if (i == (int)w1.size()) return (int)w2.size() - j;
    if (j == (int)w2.size()) return (int)w1.size() - i;
    if (w1[i] == w2[j]) return dfs(w1, w2, i + 1, j + 1);
    int insert_op = 1 + dfs(w1, w2, i, j + 1);
    int delete_op = 1 + dfs(w1, w2, i + 1, j);
    int replace_op = 1 + dfs(w1, w2, i + 1, j + 1);
    return min({insert_op, delete_op, replace_op});
}

int minDistance(string word1, string word2) {
    return dfs(word1, word2, 0, 0);
}

int main() {
    cout << minDistance("horse", "ros") << endl; // Output: 3
    return 0;
}

Line Notes

int dfs(const string& w1, const string& w2, int i, int j)Recursive function to compute edit distance from indices i and j

if (i == (int)w1.size())If word1 is exhausted, insert remaining chars of word2

if (j == (int)w2.size())If word2 is exhausted, delete remaining chars of word1

if (w1[i] == w2[j])If characters match, move both pointers without cost

int insert_op = 1 + dfs(w1, w2, i, j + 1);Try insertion operation

int delete_op = 1 + dfs(w1, w2, i + 1, j);Try deletion operation

int replace_op = 1 + dfs(w1, w2, i + 1, j + 1);Try replacement operation

return min({insert_op, delete_op, replace_op});Return minimum cost among operations

function minDistance(word1, word2) {
    function dfs(i, j) {
        if (i === word1.length) return word2.length - j;
        if (j === word2.length) return word1.length - i;
        if (word1[i] === word2[j]) return dfs(i + 1, j + 1);
        const insertOp = 1 + dfs(i, j + 1);
        const deleteOp = 1 + dfs(i + 1, j);
        const replaceOp = 1 + dfs(i + 1, j + 1);
        return Math.min(insertOp, deleteOp, replaceOp);
    }
    return dfs(0, 0);
}

// Example usage:
console.log(minDistance("horse", "ros")); // Output: 3

Line Notes

function dfs(i, j)Helper recursive function to compute edit distance from indices i and j

if (i === word1.length)If word1 is exhausted, insert remaining chars of word2

if (j === word2.length)If word2 is exhausted, delete remaining chars of word1

if (word1[i] === word2[j])If characters match, move both pointers without cost

const insertOp = 1 + dfs(i, j + 1);Try insertion operation

const deleteOp = 1 + dfs(i + 1, j);Try deletion operation

const replaceOp = 1 + dfs(i + 1, j + 1);Try replacement operation

return Math.min(insertOp, deleteOp, replaceOp);Return minimum cost among operations

⏱

Complexity

TimeO(3^(m+n))

SpaceO(m+n)

At each step, up to 3 recursive calls are made, and the recursion depth is at most m+n where m and n are string lengths.

💡 For strings of length 10, this means over 3^20 ≈ 3.5 billion calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's complexity and motivate DP.

🧠

Top-Down Memoization (Recursion + Cache)

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving performance while keeping the recursive structure.

Intuition

Store results of recursive calls in a cache keyed by indices to prevent exponential recomputation.

Algorithm

1. Initialize a 2D cache to store results for each pair of indices.
2. If result for (i, j) is cached, return it immediately.
3. Otherwise, compute recursively as in brute force and store the result in cache.
4. Return the cached result.

💡 Memoization transforms exponential recursion into polynomial time by reusing results.

</>

Code

def minDistance(word1: str, word2: str) -> int:
    from functools import lru_cache

    @lru_cache(None)
    def dfs(i, j):
        if i == len(word1):
            return len(word2) - j
        if j == len(word2):
            return len(word1) - i
        if word1[i] == word2[j]:
            return dfs(i + 1, j + 1)
        insert = 1 + dfs(i, j + 1)
        delete = 1 + dfs(i + 1, j)
        replace = 1 + dfs(i + 1, j + 1)
        return min(insert, delete, replace)

    return dfs(0, 0)

# Example usage:
if __name__ == '__main__':
    print(minDistance("horse", "ros"))  # Output: 3

Line Notes

@lru_cache(None)Caches results of dfs calls to avoid recomputation

def dfs(i, j):Recursive helper with memoization

if i == len(word1):Base case: insert remaining chars if word1 exhausted

if j == len(word2):Base case: delete remaining chars if word2 exhausted

if word1[i] == word2[j]:No operation needed if chars match

insert = 1 + dfs(i, j + 1)Try insertion

delete = 1 + dfs(i + 1, j)Try deletion

replace = 1 + dfs(i + 1, j + 1)Try replacement

return min(insert, delete, replace)Return minimum cost

import java.util.*;

public class EditDistance {
    private static Integer[][] memo;

    public static int minDistance(String word1, String word2) {
        memo = new Integer[word1.length() + 1][word2.length() + 1];
        return dfs(word1, word2, 0, 0);
    }

    private static int dfs(String w1, String w2, int i, int j) {
        if (memo[i][j] != null) return memo[i][j];
        if (i == w1.length()) return w2.length() - j;
        if (j == w2.length()) return w1.length() - i;
        if (w1.charAt(i) == w2.charAt(j)) {
            memo[i][j] = dfs(w1, w2, i + 1, j + 1);
            return memo[i][j];
        }
        int insert = 1 + dfs(w1, w2, i, j + 1);
        int delete = 1 + dfs(w1, w2, i + 1, j);
        int replace = 1 + dfs(w1, w2, i + 1, j + 1);
        memo[i][j] = Math.min(insert, Math.min(delete, replace));
        return memo[i][j];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // Output: 3
    }
}

Line Notes

private static Integer[][] memo;Memoization cache to store results for subproblems

if (memo[i][j] != null) return memo[i][j];Return cached result if available

if (i == w1.length())Base case: insert remaining chars

if (j == w2.length())Base case: delete remaining chars

if (w1.charAt(i) == w2.charAt(j))No operation needed if chars match

int insert = 1 + dfs(w1, w2, i, j + 1);Try insertion

int delete = 1 + dfs(w1, w2, i + 1, j);Try deletion

int replace = 1 + dfs(w1, w2, i + 1, j + 1);Try replacement

memo[i][j] = Math.min(insert, Math.min(delete, replace));Cache minimum cost

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> memo;

int dfs(const string& w1, const string& w2, int i, int j) {
    if (memo[i][j] != -1) return memo[i][j];
    if (i == (int)w1.size()) return (int)w2.size() - j;
    if (j == (int)w2.size()) return (int)w1.size() - i;
    if (w1[i] == w2[j]) {
        memo[i][j] = dfs(w1, w2, i + 1, j + 1);
        return memo[i][j];
    }
    int insert_op = 1 + dfs(w1, w2, i, j + 1);
    int delete_op = 1 + dfs(w1, w2, i + 1, j);
    int replace_op = 1 + dfs(w1, w2, i + 1, j + 1);
    memo[i][j] = min({insert_op, delete_op, replace_op});
    return memo[i][j];
}

int minDistance(string word1, string word2) {
    memo.assign(word1.size() + 1, vector<int>(word2.size() + 1, -1));
    return dfs(word1, word2, 0, 0);
}

int main() {
    cout << minDistance("horse", "ros") << endl; // Output: 3
    return 0;
}

Line Notes

vector<vector<int>> memo;2D vector to cache results for subproblems

if (memo[i][j] != -1) return memo[i][j];Return cached result if computed

if (i == (int)w1.size())Base case: insert remaining chars

if (j == (int)w2.size())Base case: delete remaining chars

if (w1[i] == w2[j])No operation needed if chars match

int insert_op = 1 + dfs(w1, w2, i, j + 1);Try insertion

int delete_op = 1 + dfs(w1, w2, i + 1, j);Try deletion

int replace_op = 1 + dfs(w1, w2, i + 1, j + 1);Try replacement

memo[i][j] = min({insert_op, delete_op, replace_op});Cache minimum cost

function minDistance(word1, word2) {
    const memo = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(-1));

    function dfs(i, j) {
        if (memo[i][j] !== -1) return memo[i][j];
        if (i === word1.length) return word2.length - j;
        if (j === word2.length) return word1.length - i;
        if (word1[i] === word2[j]) {
            memo[i][j] = dfs(i + 1, j + 1);
            return memo[i][j];
        }
        const insertOp = 1 + dfs(i, j + 1);
        const deleteOp = 1 + dfs(i + 1, j);
        const replaceOp = 1 + dfs(i + 1, j + 1);
        memo[i][j] = Math.min(insertOp, deleteOp, replaceOp);
        return memo[i][j];
    }

    return dfs(0, 0);
}

// Example usage:
console.log(minDistance("horse", "ros")); // Output: 3

Line Notes

const memo = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(-1));Initialize 2D cache with -1 indicating uncomputed states

if (memo[i][j] !== -1) return memo[i][j];Return cached result if available

if (i === word1.length)Base case: insert remaining chars

if (j === word2.length)Base case: delete remaining chars

if (word1[i] === word2[j])No operation needed if chars match

const insertOp = 1 + dfs(i, j + 1);Try insertion

const deleteOp = 1 + dfs(i + 1, j);Try deletion

const replaceOp = 1 + dfs(i + 1, j + 1);Try replacement

memo[i][j] = Math.min(insertOp, deleteOp, replaceOp);Cache minimum cost

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each subproblem (i,j) is computed once and stored, with m and n being string lengths.

💡 For strings of length 1000, this means about 1 million computations, which is feasible.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for large inputs and is a common interview expectation.

🧠

Bottom-Up Dynamic Programming (Tabulation)

💡 This approach builds the solution iteratively from smaller substrings, avoiding recursion overhead and making the flow easier to understand and debug.

Intuition

Create a 2D DP table where dp[i][j] represents the minimum edit distance between word1[i:] and word2[j:]. Fill the table from the bottom up.

Algorithm

1. Initialize a 2D dp array of size (m+1) x (n+1) where m and n are lengths of word1 and word2.
2. Fill the last row and last column with base cases representing empty substring transformations.
3. Iterate from bottom-right to top-left, filling dp[i][j] based on character matches and minimum operations.
4. Return dp[0][0] as the final answer.

💡 The challenge is correctly filling the table in the right order so that dependencies are already computed.

</>

Code

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][n] = m - i
    for j in range(n + 1):
        dp[m][j] = n - j

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if word1[i] == word2[j]:
                dp[i][j] = dp[i + 1][j + 1]
            else:
                dp[i][j] = 1 + min(dp[i][j + 1], dp[i + 1][j], dp[i + 1][j + 1])

    return dp[0][0]

# Example usage:
if __name__ == '__main__':
    print(minDistance("horse", "ros"))  # Output: 3

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Create DP table with extra row and column for empty substrings

for i in range(m + 1): dp[i][n] = m - iBase case: converting suffix of word1 to empty word2 requires deletions

for j in range(n + 1): dp[m][j] = n - jBase case: converting empty word1 to suffix of word2 requires insertions

for i in range(m - 1, -1, -1):Fill DP table bottom-up row-wise

for j in range(n - 1, -1, -1):Fill DP table bottom-up column-wise

if word1[i] == word2[j]: dp[i][j] = dp[i + 1][j + 1]No operation if chars match

else: dp[i][j] = 1 + min(...)Choose minimum among insert, delete, replace

return dp[0][0]Final answer is edit distance for full strings

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][n] = m - i;
        for (int j = 0; j <= n; j++) dp[m][j] = n - j;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i][j + 1], Math.min(dp[i + 1][j], dp[i + 1][j + 1]));
                }
            }
        }

        return dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // Output: 3
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];DP table with extra row and column for empty substrings

for (int i = 0; i <= m; i++) dp[i][n] = m - i;Base case: deletions to convert suffix of word1 to empty

for (int j = 0; j <= n; j++) dp[m][j] = n - j;Base case: insertions to convert empty word1 to suffix of word2

for (int i = m - 1; i >= 0; i--)Fill DP table bottom-up row-wise

for (int j = n - 1; j >= 0; j--)Fill DP table bottom-up column-wise

if (word1.charAt(i) == word2.charAt(j)) dp[i][j] = dp[i + 1][j + 1];No operation if chars match

else dp[i][j] = 1 + Math.min(...)Choose minimum among insert, delete, replace

return dp[0][0];Final answer for full strings

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int minDistance(string word1, string word2) {
    int m = (int)word1.size(), n = (int)word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) dp[i][n] = m - i;
    for (int j = 0; j <= n; j++) dp[m][j] = n - j;

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

    return dp[0][0];
}

int main() {
    cout << minDistance("horse", "ros") << endl; // Output: 3
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));DP table with extra row and column for empty substrings

for (int i = 0; i <= m; i++) dp[i][n] = m - i;Base case: deletions to empty string

for (int j = 0; j <= n; j++) dp[m][j] = n - j;Base case: insertions from empty string

for (int i = m - 1; i >= 0; i--)Fill DP table bottom-up row-wise

for (int j = n - 1; j >= 0; j--)Fill DP table bottom-up column-wise

if (word1[i] == word2[j]) dp[i][j] = dp[i + 1][j + 1];No operation if chars match

else dp[i][j] = 1 + min({dp[i][j + 1], dp[i + 1][j], dp[i + 1][j + 1]});Choose minimum operation cost

return dp[0][0];Final answer for full strings

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

    for (let i = 0; i <= m; i++) dp[i][n] = m - i;
    for (let j = 0; j <= n; j++) dp[m][j] = n - j;

    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (word1[i] === word2[j]) {
                dp[i][j] = dp[i + 1][j + 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i][j + 1], dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
    }

    return dp[0][0];
}

// Example usage:
console.log(minDistance("horse", "ros")); // Output: 3

Line Notes

const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));Initialize DP table with extra row and column

for (let i = 0; i <= m; i++) dp[i][n] = m - i;Base case: deletions to empty string

for (let j = 0; j <= n; j++) dp[m][j] = n - j;Base case: insertions from empty string

for (let i = m - 1; i >= 0; i--)Fill DP table bottom-up row-wise

for (let j = n - 1; j >= 0; j--)Fill DP table bottom-up column-wise

if (word1[i] === word2[j]) dp[i][j] = dp[i + 1][j + 1];No operation if chars match

else dp[i][j] = 1 + Math.min(...)Choose minimum operation cost

return dp[0][0];Final answer for full strings

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a 2D table of size m*n once, where m and n are string lengths.

💡 For strings of length 1000, this means about 1 million table entries, which is efficient.

Interview Verdict: Accepted

Bottom-up DP is the standard approach for edit distance in interviews due to clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i+1][*] and dp[i][j+1], we can optimize space by storing only two rows at a time.

Intuition

Use two 1D arrays to represent the current and next row of the DP table, updating iteratively to reduce space from O(m*n) to O(n).

Algorithm

1. Initialize two arrays, current and next, of length n+1.
2. Fill next with base case values for converting empty word1 suffix to word2 suffixes.
3. Iterate i from m-1 down to 0, updating current based on next and current values.
4. Swap current and next after each row iteration.
5. Return next[0] as the final answer.

💡 The key is carefully updating arrays in the correct order to maintain dependencies.

</>

Code

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    next_row = [0] * (n + 1)
    for j in range(n + 1):
        next_row[j] = n - j

    for i in range(m - 1, -1, -1):
        current = [0] * (n + 1)
        current[n] = m - i
        for j in range(n - 1, -1, -1):
            if word1[i] == word2[j]:
                current[j] = next_row[j + 1]
            else:
                current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])
        next_row = current

    return next_row[0]

# Example usage:
if __name__ == '__main__':
    print(minDistance("horse", "ros"))  # Output: 3

Line Notes

next_row = [0] * (n + 1)Initialize array for base case row

for j in range(n + 1): next_row[j] = n - jFill base case for empty word1 suffix

for i in range(m - 1, -1, -1):Iterate over word1 from end to start

current = [0] * (n + 1)Create current row array

current[n] = m - iBase case for current row last column

if word1[i] == word2[j]: current[j] = next_row[j + 1]No operation if chars match

else current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])Minimum of insert, delete, replace

next_row = currentUpdate next_row for next iteration

public class EditDistance {
    public static int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] next = new int[n + 1];
        for (int j = 0; j <= n; j++) next[j] = n - j;

        for (int i = m - 1; i >= 0; i--) {
            int[] current = new int[n + 1];
            current[n] = m - i;
            for (int j = n - 1; j >= 0; j--) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    current[j] = next[j + 1];
                } else {
                    current[j] = 1 + Math.min(current[j + 1], Math.min(next[j], next[j + 1]));
                }
            }
            next = current;
        }

        return next[0];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // Output: 3
    }
}

Line Notes

int[] next = new int[n + 1];Array to store DP values for next row

for (int j = 0; j <= n; j++) next[j] = n - j;Initialize base case for empty word1 suffix

for (int i = m - 1; i >= 0; i--)Iterate over word1 backwards

int[] current = new int[n + 1];Array for current row computations

current[n] = m - i;Base case for current row last column

if (word1.charAt(i) == word2.charAt(j)) current[j] = next[j + 1];No operation if chars match

else current[j] = 1 + Math.min(...)Minimum cost among insert, delete, replace

next = current;Update next row for next iteration

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

    for (int i = m - 1; i >= 0; i--) {
        vector<int> current(n + 1, 0);
        current[n] = m - i;
        for (int j = n - 1; j >= 0; j--) {
            if (word1[i] == word2[j]) {
                current[j] = next[j + 1];
            } else {
                current[j] = 1 + min({current[j + 1], next[j], next[j + 1]});
            }
        }
        next = current;
    }

    return next[0];
}

int main() {
    cout << minDistance("horse", "ros") << endl; // Output: 3
    return 0;
}

Line Notes

vector<int> next(n + 1, 0);Array for next row DP values

for (int j = 0; j <= n; j++) next[j] = n - j;Initialize base case for empty word1 suffix

for (int i = m - 1; i >= 0; i--)Iterate over word1 backwards

vector<int> current(n + 1, 0);Array for current row computations

current[n] = m - i;Base case for current row last column

if (word1[i] == word2[j]) current[j] = next[j + 1];No operation if chars match

else current[j] = 1 + min({current[j + 1], next[j], next[j + 1]});Minimum cost among insert, delete, replace

next = current;Update next row for next iteration

function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    let next = new Array(n + 1).fill(0);
    for (let j = 0; j <= n; j++) next[j] = n - j;

    for (let i = m - 1; i >= 0; i--) {
        let current = new Array(n + 1).fill(0);
        current[n] = m - i;
        for (let j = n - 1; j >= 0; j--) {
            if (word1[i] === word2[j]) {
                current[j] = next[j + 1];
            } else {
                current[j] = 1 + Math.min(current[j + 1], next[j], next[j + 1]);
            }
        }
        next = current;
    }

    return next[0];
}

// Example usage:
console.log(minDistance("horse", "ros")); // Output: 3

Line Notes

let next = new Array(n + 1).fill(0);Array for next row DP values

for (let j = 0; j <= n; j++) next[j] = n - j;Initialize base case for empty word1 suffix

for (let i = m - 1; i >= 0; i--)Iterate over word1 backwards

let current = new Array(n + 1).fill(0);Array for current row computations

current[n] = m - i;Base case for current row last column

if (word1[i] === word2[j]) current[j] = next[j + 1];No operation if chars match

else current[j] = 1 + Math.min(...)Minimum cost among insert, delete, replace

next = current;Update next row for next iteration

⏱

Complexity

TimeO(m*n)

SpaceO(n)

Only two arrays of length n+1 are maintained, reducing space from O(m*n) to O(n).

💡 For strings of length 1000, this reduces memory usage from millions of integers to just a few thousand.

Interview Verdict: Accepted

Space optimization is a valuable refinement in interviews, showing mastery of DP techniques.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding bottom-up DP or memoized recursion is usually best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(3^(m+n))	O(m+n)	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(m*n)	O(m*n)	Possible but less likely	Yes	Good for quick optimization of brute force
3. Bottom-Up DP	O(m*n)	O(m*n)	No	Yes	Standard approach to code
4. Space Optimized DP	O(m*n)	O(n)	No	No (without extra work)	Bonus if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force recursive approach to show understanding of the problem.Introduce memoization to optimize recursion and discuss time/space tradeoffs.Present bottom-up DP as a clean iterative solution.Optionally discuss space optimization if time permits.Write clean, tested code and walk through examples.

Time Allocation

Clarify: 3min → Approach explanation: 5min → Code: 10min → Testing & discussion: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize naive solutions, mastery of DP concepts, and coding accuracy.

Common Follow-ups

• Can you reconstruct the sequence of operations? → Use a parent pointer or backtracking from DP table.
• What if only insert and delete are allowed? → Modify DP to exclude replace operation.

💡 These follow-ups test your ability to adapt the solution and extract more information from the DP table.

🔍

Pattern Recognition

When to Use

1) Problem involves transforming one string into another 2) Allowed operations include insert, delete, replace 3) Need minimum number of operations 4) Overlapping subproblems with optimal substructure

Signature Phrases

minimum number of operationsconvert one string to anotherinsert/delete/replace characters

NOT This Pattern When

Problems that only require substring matching or counting without edits (e.g., substring search) are different.

Similar Problems

Longest Common Subsequence - related by string comparison and DPDistinct Subsequences - counts subsequence matches, uses similar DPWord Break - string segmentation with DP

Practice

1. Consider the following Python code implementing the optimal two-pointer approach for the smallest range covering k lists. Given the input nums = [[1,5,8],[4,12],[7,8,10]], what is the final smallest range returned by the function?

easy

A. [5, 7]

B. [4, 8]

C. [4, 7]

D. [7, 8]

Solution

1. Step 1: Merge and sort all elements with their list indices

   Merged array: [(1,0),(4,1),(5,0),(7,2),(8,0),(8,2),(10,2),(12,1)]

2. Step 2: Use two pointers to find minimal range covering all lists

   Sliding window covers all lists first at [4,7], then [4,8]. The range [4,7] has width 3, and [4,8] has width 4. The minimal range is [4,7].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Range [4,7] covers all lists with minimal width [OK]

Hint: Trace merged array and sliding window coverage [OK]

Common Mistakes:

• Off-by-one in window boundaries
• Forgetting to update have when shrinking window

2. What is the time complexity of the optimal space-optimized DP solution for the Best Time to Buy Sell IV problem with n days and k transactions?

medium

A. O(n * k * 2^k) due to nested recursion and state explosion

B. O(n^2 * k) because for each day it scans all previous days for transactions

C. O(k * 2^n) due to exponential subsets of transactions

D. O(n * k) because the DP iterates over days and transactions with constant holding states

Solution

1. Step 1: Identify loops in the DP code

   The DP iterates over n days in an outer loop and k transactions in an inner loop, with constant operations per iteration.

2. Step 2: Analyze recursion or nested loops

   The space-optimized DP avoids recursion stack overhead and does not scan all previous days for each day, so no quadratic factor in n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP runs in O(n*k) time, matching the nested loops over days and transactions [OK]

Hint: DP loops over days and transactions only [OK]

Common Mistakes:

• Assuming quadratic time due to scanning previous days
• Confusing recursion stack space with time complexity
• Thinking exponential subsets are enumerated

3. Examine the following modified code for Largest Rectangle in Histogram. Which line contains a subtle bug that can cause incorrect maximum area calculation?

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel to flush stack at end
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            width = i - left - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    heights.pop()  # Restore original list
    return max_area

medium

A. Line with 'while stack and heights[stack[-1]] >= h:'

B. Line with 'height = heights[stack.pop()]'

C. Line with 'width = i - left - 1'

D. Line with 'heights.append(0)'

Solution

1. Step 1: Identify condition in while loop

   The condition uses '>=' which causes bars of equal height to be popped prematurely, merging areas incorrectly.

2. Step 2: Correct condition

   Changing '>=' to '>' ensures bars of equal height remain on stack, preserving correct width calculations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '>=' pops equal height bars too early, causing wrong max area [OK]

Hint: Use '>' not '>=' to avoid premature popping [OK]

Common Mistakes:

• Using '>=' instead of '>' in while condition
• Miscomputing width boundaries
• Forgetting sentinel bar

4. Examine the following snippet from an implementation of the optimal Word Search II solution. Which line contains a subtle bug that can cause incorrect results or infinite recursion?

medium

A. Line where curr_node.word is not set to null after found

B. Line where board[r][c] is set to '#'

C. Line where curr_node.word is appended to res

D. Line where backtrack is recursively called on neighbors

Solution

1. Step 1: Identify purpose of setting curr_node.word to None

   This prevents adding the same word multiple times by marking it as found.

2. Step 2: Analyze effect of missing this line

   Without setting curr_node.word to None, duplicates can be appended and redundant searches occur, possibly causing inefficiency or infinite recursion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing word removal after found causes duplicates [OK]

Hint: Mark found words None to avoid duplicates [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Not pruning found words
• Incorrect recursion boundaries

5. Suppose the LFU cache must support a new requirement: keys can be reinserted after eviction with their previous frequency preserved. Which modification to the brute force LFU cache implementation correctly supports this feature?

hard

A. Evict keys based only on recency, ignoring frequency to avoid complexity.

B. Reset frequency to 1 on every insertion regardless of previous state to simplify logic.

C. Store frequencies persistently outside the cache and reuse them on reinsertion, updating timestamps accordingly.

D. Use a priority queue keyed by frequency and timestamp but do not update frequencies on get.

Solution

1. Step 1: Understand reinsertion with preserved frequency

   To preserve frequency on reinsertion, frequencies must be stored outside the cache entries so they survive eviction.

2. Step 2: Update timestamps on reinsertion

   When reinserting, update the timestamp to reflect recent access but keep the old frequency to maintain LFU semantics.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Persistent frequency storage and timestamp update -> correct reinsertion behavior [OK]

Hint: Preserve frequency externally and update timestamp on reinsertion [OK]

Common Mistakes:

• Resetting frequency loses LFU property
• Ignoring frequency leads to incorrect eviction
• Not updating frequency on get breaks LFU semantics