Problem Description

You are given two strings s1 and s2. Your task is to delete some characters from both strings so that the resulting strings become equal. When you delete a character, you incur a cost equal to its ASCII value. You need to find the minimum total ASCII sum of all deleted characters required to make the two strings equal.

For example, if s1 = "sea" and s2 = "eat", you could delete 's' from s1 (ASCII value 115) and delete 'a' from s2 (ASCII value 97) to make both strings equal to "ea". The total cost would be 115 + 97 = 212. However, there might be other ways to delete characters that result in a lower total cost.

The solution uses dynamic programming where f[i][j] represents the minimum ASCII sum needed to make the first i characters of s1 equal to the first j characters of s2. The algorithm builds up the solution by considering three cases:

• If characters match (s1[i-1] == s2[j-1]), no deletion is needed, so f[i][j] = f[i-1][j-1]
• If characters don't match, we either delete from s1 (cost: f[i-1][j] + ord(s1[i-1])) or delete from s2 (cost: f[i][j-1] + ord(s2[j-1]))
• The base cases handle when one string is empty, requiring all characters from the other string to be deleted

The final answer is stored in f[m][n], representing the minimum cost to make both complete strings equal.

Intuition

The key insight is recognizing this as a variant of the classic Longest Common Subsequence (LCS) problem. When we want to make two strings equal by deletion, we're essentially finding what characters they can share in common (in the same order) and deleting everything else.

Think about it this way: if we find the longest common subsequence between the two strings, those are the characters we'll keep. Everything else needs to be deleted. But unlike the standard LCS where we just count characters, here we need to track the ASCII cost of deletions.

This naturally leads to a dynamic programming approach. At each position, we face a decision: if the current characters match, great - we don't need to delete anything and can build on our previous solution. If they don't match, we must delete at least one character, and we want to choose the option with minimum cost.

The state f[i][j] represents "what's the minimum cost to make the first i characters of s1 equal to the first j characters of s2?" This subproblem structure has optimal substructure - the solution to larger problems depends on solutions to smaller problems.

The base cases are intuitive: if one string is empty, we must delete all characters from the other string, so the cost is the sum of ASCII values of all those characters. As we build up the table, each cell depends only on previously computed cells (either f[i-1][j-1] when characters match, or the minimum of f[i-1][j] and f[i][j-1] when they don't), ensuring we can solve the problem bottom-up.

The beauty of this approach is that it systematically considers all possible ways to align the strings through deletion and automatically finds the one with minimum ASCII cost.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a 2D dynamic programming approach. Let's walk through the implementation step by step:

1. Initialize the DP Table:

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

We create a 2D table f of size (m+1) × (n+1) where m = len(s1) and n = len(s2). The extra row and column handle the base cases where one string is empty.

2. Fill Base Cases - First Column:

for i in range(1, m + 1):
    f[i][0] = f[i - 1][0] + ord(s1[i - 1])

When s2 is empty (column 0), we must delete all characters from s1 up to position i. Each f[i][0] accumulates the ASCII values of all characters from s1[0] to s1[i-1].

3. Fill Base Cases - First Row:

for j in range(1, n + 1):
    f[0][j] = f[0][j - 1] + ord(s2[j - 1])

Similarly, when s1 is empty (row 0), we must delete all characters from s2 up to position j.

4. Fill the DP Table:

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if s1[i - 1] == s2[j - 1]:
            f[i][j] = f[i - 1][j - 1]
        else:
            f[i][j] = min(
                f[i - 1][j] + ord(s1[i - 1]), 
                f[i][j - 1] + ord(s2[j - 1])
            )

For each cell f[i][j], we consider two cases:

• Characters match (s1[i-1] == s2[j-1]): No deletion needed. The cost remains the same as f[i-1][j-1], which represents the cost of making the previous substrings equal.

• Characters don't match: We must delete at least one character. We have two choices:

  • Delete s1[i-1]: Cost is f[i-1][j] + ord(s1[i-1])
  • Delete s2[j-1]: Cost is f[i][j-1] + ord(s2[j-1])

  We choose the option with minimum cost.

5. Return the Result:

return f[m][n]

The bottom-right cell f[m][n] contains the minimum ASCII sum needed to make the entire strings equal.

Time Complexity: O(m × n) - we fill each cell of the 2D table exactly once.

Space Complexity: O(m × n) - for storing the DP table. This could be optimized to O(min(m, n)) since we only need the previous row to compute the current row.

Example Walkthrough

Let's walk through a small example with s1 = "sea" and s2 = "eat".

Step 1: Initialize the DP table We create a 4×4 table (since both strings have length 3, plus 1 for empty string base case).

Step 2: Fill base cases

• Row 0: If s1 is empty, delete all of s2: f[0][1] = 101 ('e'), f[0][2] = 101 + 97 = 198 ('e'+'a'), f[0][3] = 198 + 116 = 314 ('e'+'a'+'t')
• Column 0: If s2 is empty, delete all of s1: f[1][0] = 115 ('s'), f[2][0] = 115 + 101 = 216 ('s'+'e'), f[3][0] = 216 + 97 = 313 ('s'+'e'+'a')

Step 3: Fill the DP table

Initial table with base cases:

      ""   e    a    t
""     0  101  198  314
s    115   ?    ?    ?
e    216   ?    ?    ?
a    313   ?    ?    ?

Computing each cell:

• f[1][1]: 's' ≠ 'e', so min(f[0][1] + 115, f[1][0] + 101) = min(216, 216) = 216
• f[1][2]: 's' ≠ 'a', so min(f[0][2] + 115, f[1][1] + 97) = min(313, 313) = 313
• f[1][3]: 's' ≠ 't', so min(f[0][3] + 115, f[1][2] + 116) = min(429, 429) = 429
• f[2][1]: 'e' = 'e', so f[2][1] = f[1][0] = 115 (no deletion needed)
• f[2][2]: 'e' ≠ 'a', so min(f[1][2] + 101, f[2][1] + 97) = min(414, 212) = 212
• f[2][3]: 'e' ≠ 't', so min(f[1][3] + 101, f[2][2] + 116) = min(530, 328) = 328
• f[3][1]: 'a' ≠ 'e', so min(f[2][1] + 97, f[3][0] + 101) = min(212, 414) = 212
• f[3][2]: 'a' = 'a', so f[3][2] = f[2][1] = 115 (no deletion needed)
• f[3][3]: 'a' ≠ 't', so min(f[2][3] + 97, f[3][2] + 116) = min(425, 231) = 231

Final table:

      ""   e    a    t
""     0  101  198  314
s    115  216  313  429
e    216  115  212  328
a    313  212  115  231

Step 4: Result f[3][3] = 231 is our answer. This represents deleting 's' from "sea" (ASCII 115) and 't' from "eat" (ASCII 116), leaving both strings as "ea". Total cost: 115 + 116 = 231.

Note that this is actually better than our initial guess of deleting 's' and 'a' (cost 212), as the DP algorithm found that keeping "ea" as the common subsequence minimizes the total deletion cost.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the length of string s1 and n is the length of string s2.

The algorithm uses dynamic programming with a 2D table. The time complexity breaks down as follows:

• Initializing the first column takes O(m) time
• Initializing the first row takes O(n) time
• Filling the DP table requires nested loops that iterate through all m * n cells, with each cell computation taking O(1) time
• Therefore, the overall time complexity is O(m) + O(n) + O(m * n) = O(m * n)

Space Complexity: O(m * n) where m is the length of string s1 and n is the length of string s2.

The space complexity is determined by:

• The 2D DP table f of size (m + 1) × (n + 1) which stores the minimum ASCII sum of deleted characters for all subproblems
• No additional data structures that scale with input size are used
• Therefore, the space complexity is O((m + 1) * (n + 1)) = O(m * n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Mapping Between String and DP Table

One of the most common mistakes is confusion between DP table indices and string indices. The DP table uses 1-based indexing conceptually (where dp[i][j] represents the first i characters of s1 and first j characters of s2), while strings use 0-based indexing.

Incorrect Implementation:

# Wrong: Using i and j directly as string indices
if s1[i] == s2[j]:  # This will cause IndexError or wrong comparison
    dp[i][j] = dp[i - 1][j - 1]

Correct Implementation:

# Correct: Adjusting for 0-based string indexing
if s1[i - 1] == s2[j - 1]:  # i-1 and j-1 for string access
    dp[i][j] = dp[i - 1][j - 1]

2. Forgetting to Initialize Base Cases

Another pitfall is not properly initializing the first row and column of the DP table, or initializing them incorrectly.

Incorrect Implementation:

# Wrong: Forgetting to accumulate the ASCII values
for i in range(1, len_s1 + 1):
    dp[i][0] = ord(s1[i - 1])  # Should be cumulative sum

Correct Implementation:

# Correct: Accumulating ASCII values for deletion
for i in range(1, len_s1 + 1):
    dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])

3. Misunderstanding the Problem Goal

Some might mistakenly try to find the longest common subsequence and delete everything else, which doesn't guarantee the minimum ASCII sum.

Why This Approach Fails: Consider s1 = "ab" and s2 = "ba":

• LCS approach: Keep either "a" or "b", delete the other from both strings
• If we keep "a": Delete 'b' from both = 98 + 98 = 196
• If we keep "b": Delete 'a' from both = 97 + 97 = 194
• Optimal solution: Delete all characters = 97 + 98 + 98 + 97 = 390? No!
• Actually optimal: Keep empty string, delete all = 97 + 98 + 98 + 97 = 390

The correct approach is to minimize deletion cost, not maximize what we keep.

4. Space Optimization Pitfall

When optimizing space from O(m×n) to O(min(m,n)) using only two rows, a common mistake is not properly maintaining the previous row's values.

Incorrect Space-Optimized Version:

# Wrong: Overwriting values needed for next iteration
prev = [0] * (len_s2 + 1)
curr = [0] * (len_s2 + 1)
# ... after filling curr row
prev = curr  # Wrong: This creates a reference, not a copy

Correct Space-Optimized Version:

# Correct: Properly alternating between two rows
prev = [0] * (len_s2 + 1)
curr = [0] * (len_s2 + 1)
# ... after filling curr row
prev, curr = curr, prev  # Swap references
# OR use: prev = curr[:] to create a copy