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 need to design a cache system that evicts the least frequently used items first, and among those with the same frequency, evicts the least recently used. Which algorithmic approach best guarantees optimal eviction behavior for this problem?

easy

A. Maintain frequency counts and timestamps for each item, evicting the item with the lowest frequency and oldest timestamp when needed.

B. Sort all cache items by their values and evict the item with the smallest value when capacity is full.

C. Use a standard LRU cache eviction policy based on recency only, ignoring frequency counts.

D. Use a simple FIFO queue to evict the oldest inserted item when capacity is reached.

Solution

1. Step 1: Understand eviction criteria

   The problem requires evicting the least frequently used item first, and if multiple items share the same frequency, evict the least recently used among them.

2. Step 2: Identify approach that tracks frequency and recency

   Only an approach that maintains both frequency counts and timestamps can correctly identify the LFU and LRU items for eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Eviction based on frequency and recency -> correct LFU cache behavior [OK]

Hint: LFU needs frequency + recency tracking [OK]

Common Mistakes:

• Confusing LFU with LRU eviction policy
• Using FIFO which ignores frequency
• Sorting by value instead of usage metrics

2. Given a list of unique words, you need to find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] forms a palindrome. Which approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Brute force nested loops checking all pairs and verifying palindrome by concatenation

B. Building a Trie of reversed words and tracking palindrome suffixes to find pairs efficiently

C. Dynamic programming to find palindromic substrings and then pairing indices accordingly

D. Greedy approach by sorting words and pairing those with matching prefixes and suffixes

Solution

1. Step 1: Understand brute force limitations

   Brute force checks all pairs, resulting in O(n^2 * k) time, which is inefficient for large n.

2. Step 2: Recognize Trie-based optimization

   Building a Trie of reversed words allows prefix matching and palindrome suffix tracking, reducing redundant checks and achieving O(n * k^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie-based approach is known optimal for palindrome pairs [OK]

Hint: Trie with palindrome suffixes optimizes palindrome pair search [OK]

Common Mistakes:

• Assuming brute force is acceptable for large inputs
• Confusing palindrome substring DP with pair finding
• Believing greedy prefix-suffix matching suffices

3. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach by sorting envelopes by width and picking the tallest envelope at each step.

B. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search.

C. Dynamic programming with a 2D table tracking all pairs of envelopes to find the longest chain.

D. Use a graph and find the longest path by topological sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires strict increasing order in both width and height for nesting envelopes.

2. Step 2: Identify optimal approach

   Sorting by width ascending and height descending ensures envelopes with the same width do not interfere. Then LIS on heights finds the longest chain efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + LIS with binary search is the known optimal approach [OK]

Hint: Sort width asc, height desc, then LIS on heights [OK]

Common Mistakes:

• Using greedy picking tallest envelope only
• Applying LIS on widths instead of heights
• Using DP without sorting properly

4. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings, and why might a common misconception about the complexity be incorrect?

medium

A. O(n log n) because the problem is divided into halves and merged efficiently

B. O(n log n) time but O(n²) space due to storing all intermediate skylines

C. O(n log n) but with additional O(n) space overhead for recursion stack making it O(n log n) space

D. O(n²) because each merge step compares all points in both skylines

Solution

1. Step 1: Identify divide and conquer structure

   The buildings are split into halves recursively, leading to log n levels.

2. Step 2: Analyze merge cost per level

   Each merge step processes all points in the two skylines combined, which sums to O(n) per level.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) time [OK]

Hint: Divide and conquer merges cost O(n) per level over log n levels [OK]

Common Mistakes:

• Assuming merge is O(n²) due to nested loops
• Confusing recursion stack space with time complexity
• Thinking space grows quadratically due to intermediate skylines

5. Suppose the histogram bars can be reused multiple times to form rectangles (i.e., you can select the same bar multiple times consecutively). Which modification to the single pass stack-based algorithm correctly handles this variant?

hard

A. Use the same stack-based approach but remove the sentinel bar

B. Switch to a dynamic programming approach that counts repeated bars explicitly

C. Modify width calculation to include repeated bars by removing '-1' in width formula

D. No modification needed; the original algorithm already handles reuse

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means rectangles can extend beyond contiguous bars, breaking the assumption that each bar is used once in a contiguous segment.

2. Step 2: Why stack approach fails

   The stack-based method relies on contiguous bars and their indices; it cannot track multiple uses of the same bar or non-contiguous reuse.

3. Step 3: Correct approach

   A dynamic programming approach that explicitly counts repeated bars or uses a different state representation is needed to handle reuse correctly.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stack method assumes single use; DP needed for reuse [OK]

Hint: Reuse breaks contiguous assumption; DP needed [OK]

Common Mistakes:

• Thinking original stack method handles reuse
• Trying to fix width formula only
• Removing sentinel bar to fix reuse