Practice
1. The following code attempts to implement the space-optimized bottom-up DP for the Delete Operation for Two Strings problem. Which line contains a subtle bug that can cause incorrect results or index errors?
medium
Solution
Step 1: Identify indices used in inner loop
Inner loop iterates j over word2 indices; word1 index should be i, not j.Step 2: Spot incorrect character comparison
Line 10 compares word1[j] instead of word1[i], mixing indices causes wrong subproblem computations.Final Answer:
Option C -> Option CQuick Check:
Correct index usage is critical for DP correctness [OK]
Hint: Check index variables carefully in nested loops [OK]
Common Mistakes:
- Mixing i and j indices
- Incorrect base case initialization
- Wrong iteration order
2. What is the time complexity of the optimal space-optimized dynamic programming solution for counting distinct subsequences of
t in s, where m = len(s) and n = len(t)?medium
Solution
Step 1: Identify nested loops over s and t
The code iterates over all characters of s (m times) and for each, iterates over t (n times) in reverse order.Step 2: Calculate total operations
Each iteration does O(1) work, so total time is O(m * n).Final Answer:
Option C -> Option CQuick Check:
Two nested loops over lengths m and n -> O(m*n) [OK]
Hint: Nested loops over s and t imply O(m*n) time [OK]
Common Mistakes:
- Confusing recursion exponential time with DP time
- Ignoring nested loop structure
3. The following code attempts to implement the space-optimized DP for Minimum ASCII Delete Sum but contains a subtle bug:
def minimumDeleteSum(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
dp = [0] * (n + 1)
for j in range(1, n + 1):
dp[j] = dp[j-1] + ord(s2[j-1])
for i in range(1, m + 1):
prev = dp[0]
dp[0] = dp[0] + ord(s1[i-1])
for j in range(1, n + 1):
temp = dp[j]
if s1[i-1] == s2[j-1]:
dp[j] = prev
else:
dp[j] = min(dp[j] + ord(s1[i-1]), dp[j-1] + ord(s2[j-1]))
prev = temp
return dp[n]
medium
Solution
Step 1: Understand dp[0] update dependency
dp[0] must be updated before prev is assigned to preserve previous dp[0] value.Step 2: Identify bug
Assigning prev = dp[0] before dp[0] update causes prev to hold the new dp[0], corrupting dp[j] updates.Final Answer:
Option C -> Option CQuick Check:
Swapping these two lines fixes the bug [OK]
Hint: prev must hold old dp[0] before dp[0] changes [OK]
Common Mistakes:
- Updating dp[0] before saving prev value
4. 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
Solution
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.Step 2: Confirm other lines correctly implement DP transitions
Lines initializing curr, comparing characters, and updating prev are correct.Final Answer:
Option D -> Option DQuick 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
5. Suppose you want to compute the edit distance where characters can be replaced multiple times (reuse allowed) and the cost of replacement depends on character pairs. Which modification to the classic DP approach correctly handles this variant?
hard
Solution
Step 1: Understand replacement cost depends on character pairs
Replacement cost varies, so DP must incorporate a cost matrix for each character pair.Step 2: Adapt bottom-up DP to use cost matrix in dp updates
When characters differ, dp[j] updates using the specific replacement cost from the matrix, ensuring correct minimal cost.Step 3: Confirm approach handles reuse and varying costs
Bottom-up DP with cost matrix correctly accumulates minimal costs allowing multiple replacements.Final Answer:
Option A -> Option AQuick Check:
DP with cost matrix handles variable replacement costs [OK]
Hint: Incorporate cost matrix into DP transitions for variable replacements [OK]
Common Mistakes:
- Adding extra DP dimension unnecessarily
- Using memoization without cost matrix
- Trying greedy which fails globally