Edit Distance

📋

Edit Distance

Edge cases:

</>

IDE

def minDistance(word1: str, word2: str) -> int:public int minDistance(String word1, String word2)int minDistance(string word1, string word2)function minDistance(word1, word2)

def minDistance(word1: str, word2: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int minDistance(String word1, String word2) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int minDistance(string word1, string word2) {
    // Write your solution here
    return 0;
}

function minDistance(word1, word2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning 0 without computing edit distance; ignoring differences between strings.✅ Implement dp recurrence considering insert, delete, and replace operations.

Wrong: length of longer stringAssuming edit distance equals length of longer string without considering replacements or matches.✅ Use dp to find minimal operations including replacements and matches.

Wrong: off-by-one errors causing incorrect dp indexingIncorrect dp table indexing leading to wrong subproblem results.✅ Align dp indices with string indices carefully; dp[i][j] corresponds to prefixes of length i and j.

Wrong: TLEUsing brute force recursion without memoization or dp.✅ Implement bottom-up or top-down dp with memoization to achieve O(m*n) time.

✓

Test Cases

Focus on handling empty strings and single character strings correctly.

Watch out for greedy traps and indexing errors in your dp implementation.

Optimize your solution to O(m*n) time complexity to handle large inputs efficiently.

t1_01basic

Input{"word1":"horse","word2":"ros"}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Think about transforming one string to another using insert, delete, or replace operations.

💡 Use dynamic programming to consider all prefixes of both strings and their minimal edit distances.

💡 Define dp[i][j] as the edit distance between word1[:i] and word2[:j], then build up from smaller subproblems.

Why it failed: Returned wrong edit distance for canonical example; likely missed one or more operations or miscalculated dp transitions. Fix by correctly implementing dp recurrence considering insert, delete, and replace.

✓ Correctly computed minimal edit distance for canonical example.

t1_02basic

Input{"word1":"intention","word2":"execution"}

Expected5

⏱ Performance - must finish in 2000ms

intention -> inention (delete 't') -> enention (replace 'i' with 'e') -> exention (replace 'n' with 'x') -> executtion (replace 'n' with 'c') -> execution (delete 't')

💡 Try to align characters and consider operations when characters differ.

💡 Check all three operations: insert, delete, replace, and pick the minimal cost at each step.

💡 Use dp table to store intermediate results and avoid recomputation.

Why it failed: Incorrect edit distance for a longer example; possibly failed to consider all operations or misindexed dp table. Fix by carefully implementing dp with correct indices and all three operations.

✓ Correctly computed minimal edit distance for a longer example.

t2_01edge

Input{"word1":"","word2":""}

Expected0

⏱ Performance - must finish in 2000ms

Both strings empty, no operations needed.

💡 Consider base cases where one or both strings are empty.

💡 If one string is empty, the edit distance is the length of the other string.

💡 Initialize dp with base cases for empty prefixes.

Why it failed: Failed empty strings test; likely did not handle base cases properly. Fix by initializing dp[0][j] = j and dp[i][0] = i for all i,j.

✓ Correctly handled empty strings base case.

t2_02edge

Input{"word1":"a","word2":""}

Expected1

⏱ Performance - must finish in 2000ms

One string empty, other has one character; one delete operation needed.

💡 Check how your code handles single character strings compared to empty strings.

💡 Base case dp[i][0] = i covers deletions from word1.

💡 Ensure dp initialization covers single character edge cases.

Why it failed: Failed single character vs empty string; likely missing base case initialization for dp[i][0]. Fix by setting dp[i][0] = i.

✓ Correctly handled single character vs empty string.

t2_03edge

Input{"word1":"abc","word2":"abc"}

Expected0

⏱ Performance - must finish in 2000ms

Strings are identical; no operations needed.

💡 Check if your code correctly identifies when characters match and skips operations.

💡 When characters are equal, dp[i][j] = dp[i-1][j-1].

💡 Ensure no unnecessary operations are counted when characters match.

Why it failed: Failed identical strings test; likely always counting operations even when characters match. Fix by adding condition to skip operation if characters equal.

✓ Correctly handled identical strings with zero edit distance.

t2_04edge

Input{"word1":"a","word2":"b"}

Expected1

⏱ Performance - must finish in 2000ms

Strings differ by one character; one replacement needed.

💡 Check how your code handles single character differences.

💡 Replacement operation should be counted when characters differ.

💡 Ensure dp recurrence considers replace operation correctly.

Why it failed: Failed single character difference test; likely missing or miscalculating replace operation. Fix by including replace in dp recurrence.

✓ Correctly handled single character difference with one replacement.

t3_01corner

Input{"word1":"abc","word2":"acb"}

Expected2

⏱ Performance - must finish in 2000ms

Transform 'abc' to 'acb' requires two operations: replace 'b' with 'c' and replace 'c' with 'b'.

💡 Beware of greedy approaches that try to match characters in order without considering all operations.

💡 Dynamic programming considers all possible operations at each step, not just matching characters greedily.

💡 Fix greedy trap by implementing full dp recurrence considering insert, delete, and replace.

Why it failed: Greedy approach failed by underestimating operations; fix by using dp to consider all operations at each position.

✓ Correctly handled non-trivial character swaps requiring multiple operations.

t3_02corner

Input{"word1":"aaa","word2":"aaaa"}

Expected1

⏱ Performance - must finish in 2000ms

Only one insertion needed to convert 'aaa' to 'aaaa'.

💡 Check if your code confuses 0/1 edit distance with unbounded operations.

💡 Ensure insertions and deletions are counted correctly even if characters are identical.

💡 Fix by correctly implementing dp transitions for insert and delete operations.

Why it failed: Confused 0/1 vs unbounded operations; fix by correctly counting insert/delete operations even when characters match.

✓ Correctly handled insertion operation with repeated characters.

t3_03corner

Input{"word1":"abcde","word2":"abfde"}

Expected1

⏱ Performance - must finish in 2000ms

Only one replacement needed: 'c' replaced by 'f'.

💡 Check for off-by-one errors in indexing dp table.

💡 Ensure dp indices correspond correctly to string indices.

💡 Fix by carefully aligning dp indices with string characters.

Why it failed: Off-by-one error in dp indexing caused wrong result; fix by aligning dp indices with string indices properly.

✓ Correctly handled single replacement with proper indexing.

t4_01performance

Input{"word1":"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","word2":"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(m*n) = 10,000 operations expected to complete within 2 seconds.

💡 Brute force recursion is exponential and will time out here.

💡 Use bottom-up dynamic programming with O(m*n) time complexity.

💡 Optimize space by using only two rows if needed.

Why it failed: TLE due to exponential brute force recursion; fix by implementing O(m*n) DP solution.

✓ Efficient O(m*n) DP solution confirmed by passing performance test.

Practice

1. You are given a string and need to count all substrings that read the same forwards and backwards. Which approach guarantees an optimal time and space solution for this problem?

easy

A. Use a brute force approach checking every substring with nested loops and palindrome verification.

B. Use a longest common subsequence DP approach comparing the string with its reverse.

C. Expand around each character and each pair of characters to count palindromes in O(n²) time and O(1) space.

D. Apply a greedy approach by extending palindromes only when characters match at the ends.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all palindromic substrings efficiently, not just longest palindromes.

2. Step 2: Evaluate approaches

   Brute force is correct but inefficient (O(n³)). LCS DP finds longest palindrome but not count of all substrings. Greedy fails on nested palindromes. Expanding around centers counts all palindromes in O(n²) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Expanding around centers covers odd and even length palindromes efficiently [OK]

Hint: Expanding centers counts all palindromes in O(n²) time [OK]

Common Mistakes:

• Confusing longest palindrome with counting all palindromic substrings

2. You are given two sequences and need to find the length of the longest sequence that appears in both sequences in the same order, but not necessarily contiguously. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. A greedy algorithm that matches characters from left to right whenever they are equal

B. Divide and conquer by splitting sequences and merging results without overlapping

C. Sorting both sequences and then finding the longest increasing subsequence

D. Dynamic programming that builds solutions for smaller prefixes and combines them

Solution

1. Step 1: Understand the problem requirements

   The problem requires finding a subsequence common to both sequences, preserving order but not necessarily contiguous, which is a classic dynamic programming problem.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they can miss longer subsequences by making local choices. Sorting changes order and breaks subsequence constraints. Divide and conquer without overlapping subproblems cannot efficiently combine partial results. Dynamic programming systematically explores all prefixes and stores intermediate results, ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP is the standard approach for LCS problems [OK]

Hint: LCS requires DP, greedy fails on order constraints [OK]

Common Mistakes:

• Assuming greedy matching always works
• Confusing subsequence with substring
• Trying to sort sequences to simplify

3. Identify the bug in the following space-optimized DP code for longest palindromic subsequence:

medium

A. Line updating dp[j] inside the inner loop

B. Line updating prev variable

C. Line initializing dp with zeros instead of ones

D. Line comparing s[i] and s[j]

Solution

1. Step 1: Check dp initialization

   dp should be initialized with 1s because every single character is a palindrome of length 1.

2. Step 2: Consequence of zero initialization

   Initializing dp with zeros causes palindromes of length 1 to be counted as 0, leading to incorrect results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct initialization is dp = [1]*n, not zeros [OK]

Hint: dp[i][i] = 1 base case must be set [OK]

Common Mistakes:

• Forgetting base case initialization
• Overwriting dp too early
• Misusing prev variable

4. The following code attempts to implement space-optimized DP for regex matching. Which line contains a subtle bug that causes incorrect results on some inputs?

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [False] * (n + 1)
    dp[0] = True
    for j in range(2, n + 1):
        if p[j - 1] == '*':
            dp[j] = dp[j - 2]
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = False
        for j in range(1, n + 1):
            temp = dp[j]
            if p[j - 1] == '*':
                dp[j] = dp[j] or dp[j - 2]
                if p[j - 2] == '.' or p[j - 2] == s[i - 1]:
                    dp[j] = dp[j] or prev
            else:
                dp[j] = prev and (p[j - 1] == '.' or p[j - 1] == s[i - 1])
            prev = temp
    return dp[n]

medium

A. Line: dp[0] = False inside the outer loop

B. Line: for j in range(1, n + 1): iterating forwards instead of backwards

C. Line: prev = dp[0] before inner loop starts

D. Line: dp[j] = dp[j] or dp[j - 2] inside the '*' handling block

Solution

1. Step 1: Understand dp array update dependencies

   When updating dp[j], dp[j - 2] must not be overwritten before use. Iterating forwards overwrites dp[j - 2] too early.

2. Step 2: Identify iteration direction bug

   Iterating forwards causes dp[j - 2] to be stale or overwritten, leading to incorrect matches. Iterating backwards avoids this.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Known bug in space-optimized regex DP is forward iteration [OK]

Hint: DP updates with '*' require backward iteration to preserve dp[j-2] [OK]

Common Mistakes:

• Assuming forward iteration is safe in space-optimized DP

5. Examine the following buggy code for shortest common supersequence length. Which line contains the subtle bug that causes incorrect results when one input string is empty?

medium

A. Line 7: Condition comparing str1[i-1] and str2[j-1]

B. Line 5: Initialization of curr with [i] + [0]*n

C. Line 10: Updating prev = curr

D. Line 3: Initialization of prev with zeros instead of range

Solution

1. Step 1: Check base case initialization of prev array

   Prev should be initialized as range(n+1) to represent base case when str1 is empty; zeros cause incorrect base lengths.

2. Step 2: Confirm other lines correctly implement DP transitions

   Lines initializing curr, comparing characters, and updating prev are correct.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Incorrect base initialization leads to wrong results when one string is empty [OK]

Hint: Base case initialization must reflect empty string lengths [OK]

Common Mistakes:

• Initializing dp arrays with zeros instead of incremental ranges
• Mixing up indices in conditions
• Forgetting to update prev array