LeetCode 712: Minimum ASCII Delete Sum for Two Strings

Problem Restatement

We are given two strings:

s1
s2

We may delete characters from either string.

Deleting a character costs its ASCII value.

We need to make the two strings equal with the minimum total deletion cost.

Return that minimum cost.

For example, deleting "s" costs:

ord("s") = 115

The strings contain lowercase English letters, and their lengths are between 1 and 1000. The official problem asks for the lowest ASCII sum of deleted characters needed to make the two strings equal.

Input and Output

The function shape is:

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        ...

Examples

Example 1:

s1 = "sea"
s2 = "eat"

One optimal way is:

"sea" -> "ea"    delete "s", cost 115
"eat" -> "ea"    delete "t", cost 116

Total cost:

115 + 116 = 231

Output:

231

Example 2:

s1 = "delete"
s2 = "leet"

One optimal result is to make both strings equal to:

"let"

Delete "dee" from "delete":

ord("d") + ord("e") + ord("e") = 100 + 101 + 101

Delete "e" from "leet":

101

Total:

100 + 101 + 101 + 101 = 403

Output:

403

First Thought: Try All Deletions

A brute force approach is to try every possible way to delete characters from both strings.

At each position, we could:

1. Keep matching characters.
2. Delete from s1.
3. Delete from s2.

This quickly becomes exponential because the same suffix pairs are solved many times.

For strings of length up to 1000, brute force is impossible.

Key Insight

This is a dynamic programming problem.

The useful state is:

dp[i][j]

where dp[i][j] means:

Minimum ASCII deletion cost needed to make:

s1[:i]
s2[:j]

equal.

That means we solve the problem for prefixes of both strings.

The final answer is:

dp[len(s1)][len(s2)]

Recurrence

Let:

a = s1[i - 1]
b = s2[j - 1]

If the last characters match:

a == b

we do not need to delete either of them.

So:

dp[i][j] = dp[i - 1][j - 1]

If they do not match, we have two choices.

Delete a from s1:

dp[i - 1][j] + ord(a)

Delete b from s2:

dp[i][j - 1] + ord(b)

Take the cheaper option:

dp[i][j] = min(
    dp[i - 1][j] + ord(a),
    dp[i][j - 1] + ord(b),
)

Base Cases

If s2 is empty, we must delete all characters from s1[:i].

dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])

If s1 is empty, we must delete all characters from s2[:j].

dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])

Also:

dp[0][0] = 0

Two empty strings already match.

Algorithm

1. Let m = len(s1) and n = len(s2).
2. Create a DP table of size (m + 1) x (n + 1).
3. Fill the first column by deleting from s1.
4. Fill the first row by deleting from s2.
5. For every i from 1 to m:
   • For every j from 1 to n:
     • If s1[i - 1] == s2[j - 1], copy dp[i - 1][j - 1].
     • Otherwise, choose the cheaper deletion.
6. Return dp[m][n].

Correctness

We prove that dp[i][j] stores the minimum deletion cost needed to make s1[:i] and s2[:j] equal.

For the base cases, if one prefix is empty, the only way to make the strings equal is to delete every character from the other prefix. The initialization sums exactly those ASCII costs, so the base cases are correct.

For non-empty prefixes, consider the last characters s1[i - 1] and s2[j - 1].

If they are equal, an optimal solution can keep both characters at the end. Then we only need to make the earlier prefixes s1[:i - 1] and s2[:j - 1] equal. This costs dp[i - 1][j - 1].

If they are different, they cannot both remain as the final matching character. At least one of them must be deleted. If we delete s1[i - 1], the remaining cost is dp[i - 1][j] + ord(s1[i - 1]). If we delete s2[j - 1], the remaining cost is dp[i][j - 1] + ord(s2[j - 1]). Taking the minimum gives the best possible cost.

Thus every DP state is computed correctly from smaller correct states. Therefore dp[m][n] is the minimum cost for the full strings.

Complexity

Let:

m = len(s1)
n = len(s2)

Implementation

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = len(s2)

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

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

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

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

                    dp[i][j] = min(delete_from_s1, delete_from_s2)

        return dp[m][n]

Code Explanation

First, get the string lengths:

m = len(s1)
n = len(s2)

Create the DP table:

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

Initialize the first column:

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

This means s2 is empty, so we delete all characters from s1.

Initialize the first row:

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

This means s1 is empty, so we delete all characters from s2.

For matching last characters:

if s1[i - 1] == s2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]

No deletion is needed for those two characters.

For different last characters:

delete_from_s1 = dp[i - 1][j] + ord(s1[i - 1])
delete_from_s2 = dp[i][j - 1] + ord(s2[j - 1])

Choose the cheaper deletion:

dp[i][j] = min(delete_from_s1, delete_from_s2)

Finally:

return dp[m][n]

Space-Optimized Implementation

Each DP row only depends on the previous row and the current row.

So we can reduce space from O(mn) to O(n).

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = 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_diagonal = dp[0]
            dp[0] += ord(s1[i - 1])

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

                if s1[i - 1] == s2[j - 1]:
                    dp[j] = prev_diagonal
                else:
                    delete_from_s1 = dp[j] + ord(s1[i - 1])
                    delete_from_s2 = dp[j - 1] + ord(s2[j - 1])
                    dp[j] = min(delete_from_s1, delete_from_s2)

                prev_diagonal = old_dp_j

        return dp[n]

Testing

def test_minimum_delete_sum():
    s = Solution()

    assert s.minimumDeleteSum("sea", "eat") == 231
    assert s.minimumDeleteSum("delete", "leet") == 403
    assert s.minimumDeleteSum("a", "a") == 0
    assert s.minimumDeleteSum("a", "b") == ord("a") + ord("b")
    assert s.minimumDeleteSum("abc", "abc") == 0
    assert s.minimumDeleteSum("abc", "def") == sum(map(ord, "abcdef"))

    print("all tests passed")

test_minimum_delete_sum()

Test coverage: