Delete Operation for Two Strings

▶

Steps

setup

Initialize dp array length

Create a dp array of length n+1 (4) initialized with zeros to represent the base case for suffixes of word2.

💡 Initializing dp array size is crucial to store results for all suffixes of word2 including the empty suffix.

Line:

dp = [0] * (n + 1)

💡 The dp array length corresponds to all suffixes of word2, including the empty suffix at index n.

setup

Fill base case for empty suffix of word1

Fill dp[j] with the number of deletions needed when word1 suffix is empty, which is the length of word2 suffix starting at j.

💡 This base case means if word1 is empty, we must delete all remaining characters in word2 suffix.

Line:

for j in range(n + 1):
    dp[j] = n - j

💡 dp[j] now holds the cost of deleting all characters from word2[j:] to match empty word1 suffix.

fill_row

Start outer loop: i = 2 (word1 char 'a')

Begin processing suffix starting at i=2 ('a') in word1. Store dp[n] (dp[3]) in prev and update dp[n] to m - i (1).

💡 Updating dp[n] sets the cost when word2 suffix is empty and word1 suffix is non-empty.

Line:

prev = dp[n]
dp[n] = m - i

💡 dp[n] now reflects the cost of deleting remaining characters in word1 suffix when word2 suffix is empty.

fill_cells

Inner loop j=2: compare word1[2]='a' and word2[2]='t'

Compare characters 'a' and 't'. They differ, so update dp[2] = 1 + min(dp[2], dp[3]) = 1 + min(1,1) = 2.

💡 When characters differ, we consider deleting from either string and take the minimal cost plus one deletion.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 This step shows how mismatches increase deletion cost by 1 plus the minimal future cost.

fill_cells

Inner loop j=1: compare word1[2]='a' and word2[1]='a'

Characters match ('a' == 'a'), so dp[1] = prev (which is dp[3] before update, value 1).

💡 Matching characters mean no deletion needed here; cost is carried over from dp[j+1] of previous iteration.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Matching characters allow skipping deletions, reducing cost.

fill_cells

Inner loop j=0: compare word1[2]='a' and word2[0]='e'

Characters differ ('a' != 'e'), so dp[0] = 1 + min(dp[0], dp[1]) = 1 + min(3,1) = 2.

💡 Choosing the minimal deletion path between deleting from word1 or word2 suffixes.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 This step shows how the algorithm chooses the cheaper deletion path.

fill_row

Start outer loop: i = 1 (word1 char 'e')

Set prev = dp[n] (dp[3] = 1), update dp[n] = m - i = 2 for suffix starting at i=1.

💡 Updating dp[n] sets cost for empty suffix of word2 with non-empty suffix of word1.

Line:

prev = dp[n]
dp[n] = m - i

💡 dp[n] reflects cost of deleting remaining characters in word1 suffix when word2 suffix is empty.

fill_cells

Inner loop j=2: compare word1[1]='e' and word2[2]='t'

Characters differ ('e' != 't'), so dp[2] = 1 + min(dp[2], dp[3]) = 1 + min(2,2) = 3.

💡 Mismatch increases deletion cost by 1 plus minimal future cost.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Shows how mismatches accumulate deletion cost.

fill_cells

Inner loop j=1: compare word1[1]='e' and word2[1]='a'

Characters differ ('e' != 'a'), so dp[1] = 1 + min(dp[1], dp[2]) = 1 + min(1,3) = 2.

💡 Choosing minimal deletion path between suffixes.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Algorithm picks cheaper deletion option.

fill_cells

Inner loop j=0: compare word1[1]='e' and word2[0]='e'

Characters match ('e' == 'e'), so dp[0] = prev (previous dp[1]) = 1.

💡 Matching characters allow skipping deletions, cost carried over.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Matching characters reduce deletion cost.

fill_row

Start outer loop: i = 0 (word1 char 's')

Set prev = dp[n] (dp[3] = 2), update dp[n] = m - i = 3 for suffix starting at i=0.

💡 Updating dp[n] sets cost for empty suffix of word2 with non-empty suffix of word1.

Line:

prev = dp[n]
dp[n] = m - i

💡 dp[n] reflects cost of deleting remaining characters in word1 suffix when word2 suffix is empty.

fill_cells

Inner loop j=2: compare word1[0]='s' and word2[2]='t'

Characters differ ('s' != 't'), so dp[2] = 1 + min(dp[2], dp[3]) = 1 + min(3,3) = 4.

💡 Mismatch increases deletion cost by 1 plus minimal future cost.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Shows how mismatches accumulate deletion cost.

fill_cells

Inner loop j=1: compare word1[0]='s' and word2[1]='a'

Characters differ ('s' != 'a'), so dp[1] = 1 + min(dp[1], dp[2]) = 1 + min(2,4) = 3.

💡 Choosing minimal deletion path between suffixes.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Algorithm picks cheaper deletion option.

fill_cells

Inner loop j=0: compare word1[0]='s' and word2[0]='e'

Characters differ ('s' != 'e'), so dp[0] = 1 + min(dp[0], dp[1]) = 1 + min(1,3) = 2.

💡 Choosing minimal deletion path between suffixes.

Line:

temp = dp[j]
if word1[i] == word2[j]:
    dp[j] = prev
else:
    dp[j] = 1 + min(dp[j], dp[j + 1])
prev = temp

💡 Algorithm picks cheaper deletion option.

reconstruct

Return final answer dp[0]

After processing all characters, dp[0] holds the minimum number of deletions needed to make the two strings equal.

💡 The final dp[0] value is the answer to the problem.

Line:

return dp[0]

💡 dp[0] = 2 means two deletions are needed to make 'sea' and 'eat' equal.

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [0] * (n + 1)  # STEP 1
    for j in range(n + 1):  # STEP 2
        dp[j] = n - j
    for i in range(m - 1, -1, -1):  # STEP 3,7,11
        prev = dp[n]  # STEP 3,7,11
        dp[n] = m - i  # STEP 3,7,11
        for j in range(n - 1, -1, -1):  # STEP 4-6,8-10,12-14
            temp = dp[j]  # STEP 4,8,12
            if word1[i] == word2[j]:  # STEP 5,9,13
                dp[j] = prev  # STEP 5,9,13
            else:
                dp[j] = 1 + min(dp[j], dp[j + 1])  # STEP 6,10,14
            prev = temp  # STEP 6,10,14
    return dp[0]  # STEP 15

📊

Delete Operation for Two Strings - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm builds the solution from the bottom up, making it easier to understand the logic behind the minimum deletions calculation.

Initializing dp array

i\w	0	1	2	3
i=0	0	0	0	0

dp array initialized

Initializing dp array

i\w	0	1	2	3
i=0	3	2	1	0

base case dp values

Item 2 - wt:0 val:1

i\w	0	1	2	3
i=0	3	2	1	1

dp[n] updated

Item 2 - wt:2 val:2

i\w	0	1	2	3
i=0	3	2	2	1

dp[2] updated

Item 2 - wt:1 val:1

i\w	0	1	2	3
i=0	3	1	2	1

dp[1] updated

Item 2 - wt:2 val:2

i\w	0	1	2	3
i=0	2	1	2	1

dp[0] updated

Item 1 - wt:0 val:2

i\w	0	1	2	3
i=0	2	1	2	2

dp[n] updated

Item 1 - wt:3 val:3

i\w	0	1	2	3
i=0	2	1	3	2

dp[2] updated

Item 1 - wt:2 val:2

i\w	0	1	2	3
i=0	2	2	3	2

dp[1] updated

Item 1 - wt:1 val:1

i\w	0	1	2	3
i=0	1	2	3	2

dp[0] updated

Item 0 - wt:0 val:3

i\w	0	1	2	3
i=0	1	2	3	3

dp[n] updated

Item 0 - wt:4 val:4

i\w	0	1	2	3
i=0	1	2	4	3

dp[2] updated

Item 0 - wt:3 val:3

i\w	0	1	2	3
i=0	1	3	4	3

dp[1] updated

Item 0 - wt:2 val:2

i\w	0	1	2	3
i=0	2	3	4	3

dp[0] updated

Initializing dp array

i\w	0	1	2	3
i=0	2	3	4	3

final answer

Key Takeaways

✓ The dp array represents minimal deletions for suffixes of word2 at each step of iterating word1 backwards.

This insight is hard to see from code alone because the dp array is updated in place and backwards, which can be confusing without visualization.

✓ Matching characters allow the algorithm to carry over previous costs without adding deletions, reducing the total cost.

Seeing the dp update directly when characters match clarifies why the algorithm avoids unnecessary deletions.

✓ When characters differ, the algorithm chooses the minimal deletion path between deleting from word1 or word2 suffixes, adding one to the minimal future cost.

The visualization shows concrete examples of this decision, making the branching logic clear.

Practice

1. Given the following code for computing edit distance, what is the value of dp[3] after the inner loop finishes when word1 = 'abc' and word2 = 'ac' during the second iteration of the outer loop (i=2)?

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace dp array initialization and first iteration

   Initially dp = [0,1,2]. After i=1 (word1[0]='a'), dp updates to [1,0,1].

2. Step 2: Trace second iteration i=2 (word1[1]='b')

   Start dp[0]=2. For j=1 (word2[0]='a'), chars differ, dp[1]=min(0+1,2+1,1+1)=1. For j=2 (word2[1]='c'), chars differ, dp[2]=min(1+1,1+1,0+1)=1. So dp after inner loop: [2,1,1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual step-by-step matches dp[3]=2 [OK]

Hint: Track dp updates carefully for each i,j iteration [OK]

Common Mistakes:

• Off-by-one indexing
• Confusing prev and temp variables
• Mis-updating dp[0]

2. Consider the following code snippet for finding the longest palindromic substring using dynamic programming. What is the value of max_len after processing the input s = "abba"?

easy

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace dp for input "abba"

   Single chars dp[i][i] = True, max_len=1. For length=2, "ab" dp[0][1]=False, "bb" dp[1][2]=True, max_len=2. For length=3, "abb" dp[0][2]=False, "bba" dp[1][3]=False. For length=4, "abba" dp[0][3]=True (since s[0]==s[3] and dp[1][2]=True), max_len=4.

2. Step 2: Confirm max_len update

   max_len updated to 2 at "bb", then to 4 at "abba".

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest palindrome is "abba" length 4 [OK]

Hint: Check dp updates for length 4 substring "abba" [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Missing even length palindrome updates
• Confusing max_len update condition

3. Consider the following buggy code for the space-optimized edit distance. Which line contains the subtle bug that causes incorrect results for empty strings or boundary cases?

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = 0  # Bug here
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev + 1)
            prev = temp
    return dp[n]

medium

A. Line 4: dp = list(range(n + 1))

B. Line 6: prev = dp[0]

C. Line 7: dp[0] = 0 # Bug here

D. Line 11: dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev + 1)

Solution

1. Step 1: Understand dp[0] initialization role

   dp[0] represents cost of deleting all characters from word1 prefix to match empty word2 prefix, so it must be i, not 0.

2. Step 2: Identify incorrect dp[0] reset

   Setting dp[0] = 0 inside loop resets deletion cost incorrectly, breaking base case for empty prefixes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct dp[0] update is dp[0] = i [OK]

Hint: dp[0] must track deletions, so dp[0] = i each iteration [OK]

Common Mistakes:

• Resetting dp[0] to zero
• Confusing prev and temp
• Misindexing dp array

4. 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)

5. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the shortest common supersequence problem, where the input strings have lengths m and n?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m^2 + n^2)

Solution

1. Step 1: Identify nested loops over m and n in the DP code

   The outer loop runs m times, inner loop runs n times, each iteration constant work.

2. Step 2: Confirm no extra multiplicative factors from recursion or auxiliary structures

   Space optimization reduces space but does not affect time complexity, which remains O(m*n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table filling requires m*n steps, no hidden extra loops [OK]

Hint: DP with two nested loops over m and n -> O(m*n) time [OK]

Common Mistakes:

• Confusing space with time complexity
• Assuming recursion stack adds multiplicative factor
• Thinking linear time is possible