Minimum ASCII Delete Sum for Two Strings: DP on String Pairs

You are given two strings s1 and s2. Find the lowest ASCII sum of deleted characters to make the two strings equal. Each deletion costs the ASCII value of the character you remove.

This is LeetCode 712: Minimum ASCII Delete Sum for Two Strings. For example, s1 = "sea" and s2 = "eat" returns 231. You delete 's' from "sea" (ASCII 115) and 't' from "eat" (ASCII 116), leaving "ea" in both strings. Total cost: 115 + 116 = 231. If you have solved Delete Operation for Two Strings or Edit Distance, you will recognize the 2D table immediately. The twist here is that each deletion has a weight equal to the character's ASCII value.

Why this problem matters

The delete operation problem (LeetCode 583) counts the number of deletions. This problem asks you to minimize the total cost of those deletions. That single change turns a counting problem into an optimization problem with weighted transitions. It is a great test of whether you truly understand the 2D string DP pattern rather than just memorizing a template.

In interviews, this problem checks whether you can adapt a known pattern to a new cost model. The table shape is identical to LCS and edit distance, but the base cases and recurrence both change because deletions are no longer free.

The DP approach

Define dp[i][j] as the minimum ASCII delete sum needed to make s1[:i] and s2[:j] equal. The table has (m + 1) rows and (n + 1) columns.

Base cases:

• dp[0][0] = 0. Two empty strings are already equal.
• dp[i][0] = dp[i-1][0] + ord(s1[i-1]). To match the empty string, delete all characters from s1[:i].
• dp[0][j] = dp[0][j-1] + ord(s2[j-1]). To match the empty string, delete all characters from s2[:j].

Recurrence:

• If s1[i-1] == s2[j-1], the characters match for free: dp[i][j] = dp[i-1][j-1].
• Otherwise, we must delete at least one character. Pick the cheaper option:
  • Delete s1[i-1]: dp[i-1][j] + ord(s1[i-1])
  • Delete s2[j-1]: dp[i][j-1] + ord(s2[j-1])
  • Take the minimum.

Python solution

def minimum_delete_sum(s1, s2):
    m, n = len(s1), 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:
                dp[i][j] = min(
                    dp[i - 1][j] + ord(s1[i - 1]),
                    dp[i][j - 1] + ord(s2[j - 1]),
                )

    return dp[m][n]

Space-optimized solution

Just like edit distance and LCS, each row only depends on the current row and the previous row. You can drop the full grid down to two 1D arrays. When characters match, grab prev[j-1] (the diagonal). Otherwise, take the min of prev[j] (above) and curr[j-1] (left).

def minimum_delete_sum(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    for j in range(1, n + 1):
        prev[j] = prev[j - 1] + ord(s2[j - 1])

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

    return prev[n]

Step-by-step walkthrough

Let's trace through s1 = "sea" and s2 = "eat" to see exactly how the table fills in.

The answer is dp[3][3] = 231. We deleted 's' (115) and 't' (116), keeping "ea" as the common surviving string.

Complexity analysis

Where m = length of s1 and n = length of s2.

Building blocks

This problem is built on two reusable pieces:

1. Two-string DP table. The (m+1) x (n+1) grid where dp[i][j] compares prefixes of both strings. You see this same skeleton in LCS, edit distance, and the delete operation problem. The key is recognizing the three neighbors (diagonal, above, left) and what each one represents.

2. Weighted transitions. Instead of counting deletions (each costing 1), every deletion costs ord(char). This changes the base cases from simple indices to cumulative ASCII sums, and changes the recurrence from +1 to +ord(char). Once you see this generalization, you can adapt any unweighted string DP to a weighted variant.

Edge cases

• One or both strings empty. If s1 is empty, you must delete all of s2, so the answer is the sum of all ASCII values in s2 (and vice versa).
• Identical strings. Every character matches on the diagonal, so dp[m][n] = 0. No deletions needed.
• No common characters. You must delete everything from both strings. The answer equals the sum of all ASCII values in s1 plus all ASCII values in s2.
• Single character strings. If s1 = "a" and s2 = "a", the answer is 0. If s1 = "a" and s2 = "b", the answer is ord("a") + ord("b") = 195.

From understanding to recall

You now know how to fill the DP table, why matching characters get a free diagonal pass, and how weighted deletions change the base cases and recurrence. But solving it once with the explanation in front of you is different from writing it cold in an interview. You need to set up the (m+1) x (n+1) table from memory, get the ASCII-sum base cases right, and explain why there is no replace operation.

This problem sits in the two-string DP family alongside LCS, edit distance, and the unweighted delete operation. Each variant changes what the cell stores and how the recurrence combines neighbors. Drilling all four until the differences are automatic is how you build real fluency. The two-string-dp building block is one of roughly 60 reusable patterns in the CodeBricks system, where spaced repetition helps you move from "I understand the solution" to "I can write it from scratch."

Related posts

• Edit Distance - The classic three-operation variant of 2D string DP. Same table structure, but with insertions and replacements added.
• Longest Common Subsequence - The foundation of two-string DP. Maximize shared subsequence length instead of minimizing deletion cost.
• Delete Operation for Two Strings - The unweighted version of this problem. Count deletions instead of summing ASCII values.