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 function implementing a space-optimized DP for longest common substring. What is the returned value when called with s1 = 'abc' and s2 = 'xbc'?

def longest_common_substring_space_optimized(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(m, 0, -1):
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace dp array updates for i=1 (s1[0]='a')

   Compare 'a' with 'c','b','x' in s2 backwards: no matches, dp remains zeros.

2. Step 2: Trace dp updates for i=2 (s1[1]='b') and i=3 (s1[2]='c')

   At i=2, j=2 matches 'b' == 'b', dp[2] = dp[1]+1=1; max_len=1. At i=3, j=3 matches 'c' == 'c', dp[3] = dp[2]+1=2; max_len=2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Longest common substring is 'bc' length 2 [OK]

Hint: Trace dp updates backward to avoid overwriting [OK]

Common Mistakes:

• Iterating dp forward overwrites needed values
• Off-by-one indexing errors
• Confusing max_len update timing

2. You are given a string and need to find the length of the longest subsequence that reads the same forwards and backwards. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach selecting matching characters from both ends

B. Sorting the string and then finding the longest common subsequence with the original

C. Divide and conquer by splitting the string into halves and merging results

D. Dynamic Programming using bottom-up tabulation to build solutions for substrings

Solution

1. Step 1: Understand problem requires subsequence, not substring

   Greedy or sorting approaches fail because subsequences can skip characters and order matters.

2. Step 2: Recognize overlapping subproblems and optimal substructure

   Dynamic programming bottom-up tabulation efficiently computes longest palindromic subsequence by building from smaller substrings.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP tabulation is standard for longest palindromic subsequence [OK]

Hint: Longest palindromic subsequence requires DP, not greedy [OK]

Common Mistakes:

• Assuming greedy approach works
• Confusing subsequence with substring
• Trying to sort string for solution

3. What is the time complexity of the dynamic programming solution for the longest palindromic substring problem, and why?

medium

A. O(n^2) because the DP table of size nxn is filled once

B. O(n) because each character is processed once

C. O(n^3) because each substring is checked with a nested loop and palindrome check

D. O(n^2) but with extra O(n) recursion stack space

Solution

1. Step 1: Identify loops in DP solution

   Two nested loops: outer over substring length (up to n), inner over start index (up to n), total O(n^2).

2. Step 2: Confirm no extra recursion or nested palindrome checks

   Palindrome check is O(1) via DP table lookup, no recursion stack used.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size nxn filled once -> O(n^2) time [OK]

Hint: DP fills nxn table once, no recursion [OK]

Common Mistakes:

• Confusing brute force O(n^3) with DP
• Assuming recursion stack adds O(n) space
• Thinking each substring palindrome check is O(n)

4. The following code attempts to find the longest palindromic substring using DP. Identify the line containing the subtle bug that causes incorrect results for some inputs.

medium

A. Line: if length < 3:

B. Line: dp[i][i] = True

C. Line: dp[i][j] = dp[i + 1][j - 1]

D. Line: for i in range(n - length + 1):

Solution

1. Step 1: Compare condition with correct code

   The correct condition is length <= 3, but here it is length < 3, so length=3 substrings are not handled correctly.

2. Step 2: Understand impact

   For length=3, dp[i][j] should be True if s[i]==s[j], but this code skips that, causing missed palindromes of length 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing < to <= fixes the bug [OK]

Hint: Check boundary conditions for length 3 palindromes [OK]

Common Mistakes:

• Off-by-one in length condition
• Confusing substring indices
• Incorrect DP table initialization

5. What is the time and space complexity of the space-optimized bottom-up DP solution for the Minimum ASCII Delete Sum problem, given strings of lengths m and n?

medium

A. Time: O(m+n), Space: O(m+n)

B. Time: O(m*n), Space: O(n)

C. Time: O(m*n), Space: O(m*n)

D. Time: O(2^(m+n)), Space: O(m+n)

Solution

1. Step 1: Identify nested loops

   Outer loop runs m times, inner loop runs n times -> total O(m*n) time.

2. Step 2: Analyze space usage

   Only one dp array of size n+1 is used, so space is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Matches known DP optimization for string problems [OK]

Hint: Nested loops multiply time; dp array size defines space [OK]

Common Mistakes:

• Confusing recursion stack space with DP array space