How to Solve: Edit Distance (Levenshtein Distance) – Complete Guide for FAANG Interviews

How to Solve: Edit Distance (Levenshtein Distance) – Complete Guide for FAANG Interviews

? Introduction

"This single problem tests recursion, dynamic programming, and space optimization—master it, and you’ll crush 1 in 4 DP questions in FAANG onsites."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Edit Distance, ensure you understand: 1. Recursion & Memoization – Breaking problems into smaller subproblems. 2. Dynamic Programming (DP) Basics – Overlapping subproblems, optimal substructure. 3. 2D DP Tables – Storing intermediate results in a grid.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you see an Edit Distance problem:

1. Clarify the Problem
2. Confirm allowed operations: Insert, Delete, Replace (standard Levenshtein).

3. Ask: "Are substitutions allowed? Is cost uniform (1 per op)?"

4. Define Subproblem

5. Let dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1].

6. Base Cases

7. If word1 is empty (i=0), insert all j chars of word2 → dp[0][j] = j.

8. If word2 is empty (j=0), delete all i chars of word1 → dp[i][0] = i.

9. Recurrence Relation

10. If word1[i-1] == word2[j-1] → No operation needed → dp[i][j] = dp[i-1][j-1].

11. Else → Take min of 3 operations + 1:

    • Insert: dp[i][j-1]
    • Delete: dp[i-1][j]
    • Replace: dp[i-1][j-1]

12. Choose Approach

13. Recursive + Memoization (Top-down) → Good for small inputs, intuitive.

14. Bottom-Up DP (Tabulation) → Preferred for interviews (avoids stack overflow).

15. Optimize Space (Follow-up)

16. Use two 1D arrays (prev and curr) instead of full 2D table.

17. Edge Cases

18. One string is empty.
19. Both strings are identical.

20. One string is a subsequence of the other.

21. Code & Test

22. Write the DP table initialization.
23. Fill the table iteratively.
24. Return dp[m][n].

? WORKED EXAMPLES

Example 1 – Basic (Levenshtein Distance)

Problem: Given two strings word1 and word2, return the minimum number of operations to convert word1 to word2.

Solution (Bottom-Up DP):

def minDistance(word1: str, word2: str) -> int:

    m, n = len(word1), len(word2)

    dp = [[0]  (n + 1) for _ in range(m + 1)]


    # Base cases

    for i in range(m + 1):

        dp[i][0] = i

    for j in range(n + 1):

        dp[0][j] = j


    for i in range(1, m + 1):

        for j in range(1, n + 1):

            if word1[i-1] == word2[j-1]:

                dp[i][j] = dp[i-1][j-1]

            else:

                dp[i][j] = 1 + min(dp[i-1][j],    # Delete

                                   dp[i][j-1],    # Insert

                                   dp[i-1][j-1])  # Replace

    return dp[m][n]

Time Complexity: O(mn) (filling a 2D table). Space Complexity: O(mn) (can be optimized to O(n)).

Why This Works: - The DP table tracks the min operations for all prefixes of word1 and word2. - If characters match, we carry forward the previous result (dp[i-1][j-1]). - If they differ, we take the cheapest of the 3 possible operations.

Example 2 – Medium (Space Optimization)

Problem: Solve the same problem, but optimize space to O(n).

Solution (1D DP):

def minDistance(word1: str, word2: str) -> int:

    m, n = len(word1), len(word2)

    prev = [j for j in range(n + 1)]


    for i in range(1, m + 1):

        curr = [0]  (n + 1)

        curr[0] = i

        for j in range(1, n + 1):

            if word1[i-1] == word2[j-1]:

                curr[j] = prev[j-1]

            else:

                curr[j] = 1 + min(prev[j],      # Delete

                                  curr[j-1],    # Insert

                                  prev[j-1])    # Replace

        prev = curr

    return prev[n]

Time Complexity: O(mn). Space Complexity: O(n) (only two 1D arrays).

Why This Works: - We only need the previous row (prev) to compute the current row (curr). - This reduces space from O(mn) → O(n) without changing the logic.

Example 3 – Hard (Follow-up: Unequal Operation Costs)

Problem: Suppose insert/delete costs 1, but replace costs 2. Modify the solution.

Solution:

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][0] = i

    for j in range(n + 1):

        dp[0][j] = j


    for i in range(1, m + 1):

        for j in range(1, n + 1):

            if word1[i-1] == word2[j-1]:

                dp[i][j] = dp[i-1][j-1]

            else:

                dp[i][j] = min(

                    dp[i-1][j] + 1,      # Delete

                    dp[i][j-1] + 1,      # Insert

                    dp[i-1][j-1] + 2     # Replace (cost = 2)

                )

    return dp[m][n]

Time Complexity: O(mn). Space Complexity: O(mn).

Why This Works: - The only change is adjusting the replace cost from 1 to 2. - The DP transition remains the same, but weights are updated.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. Edit Distance is a classic DP problem where you convert one string to another using insert, delete, or replace. Here’s the playbook:

1. Define dp[i][j] as the min operations to convert word1[0..i-1] to word2[0..j-1].
2. Base cases: If one string is empty, the answer is the length of the other.
3. Recurrence: If characters match, carry forward dp[i-1][j-1]. If not, take the min of insert, delete, or replace + 1.
4. Optimize space by using two 1D arrays instead of a full 2D table.
5. Test edge cases: Empty strings, identical strings, and subsequences.

This pattern shows up in spell checkers, DNA sequencing, and even plagiarism detection. Nail it, and you’ll handle any DP string problem thrown at you. Now go crush that interview!

? Final Notes

• Practice: Solve "Edit Distance" on LeetCode (Problem #72) and "One Edit Distance" (Problem #161).
• Follow-ups: Be ready for space optimization and unequal operation costs.
• Whiteboard Tip: Draw the DP table for small inputs (e.g., "horse" → "ros") to visualize the transitions.

This guide is 100% interview-ready—every line is actionable under pressure. Good luck! ?