Domain 2MediumMEDIUM

Minimum ASCII Delete Sum for Two Strings

LeetCode problem 712: Minimum ASCII Delete Sum for Two Strings (medium).

Domain: medium•Updated: 2026-08-30
#Dynamic Programming

Problem Breakdown

We are given two strings, s1 and s2. Our objective is to transform both strings into a common subsequence by deleting characters from them. The cost of this transformation is defined as the sum of ASCII values of all deleted characters. We need to minimize this total cost.

  • Inputs: Two strings s1, s2 containing lowercase English letters (ASCII 97-122).
  • Output: An integer representing the minimum possible deletion sum.
  • Constraints: String lengths are between 0 and 1000. Since characters are standard ASCII, overflow is not a concern for standard integers (1000×1281000 \times 128 fits easily in a 32-bit int).

Tricky Edge Cases:

  • Empty strings: If one string is empty initially, we must delete all characters from the other. The DP base cases handle this naturally.
  • No common subsequence possible (e.g., “abc”, “def”): We end up deleting everything from both strings.
  • Identical strings: Cost should be 0.

Intuition

A brute-force approach would involve trying every combination of deletions to find the longest matching sequence, but that is exponential in complexity (O(3N)O(3^N) roughly), which will time out for N=1000N=1000.

This problem shares structural similarities with Longest Common Subsequence (LCS). In standard LCS, we maximize length. Here, we want to minimize deletion cost.

  • If characters match (s1[i] == s2[j]), it is optimal to keep them in the common subsequence because deleting either would incur a positive ASCII cost without benefit. The state transitions from dp[i-1][j-1].
  • If they don’t match, we have two choices: delete character from s1 or delete character from s2. We take the minimum of these paths plus their respective costs.

This suggests a Dynamic Programming approach where dp[i][j] stores the min cost to make prefixes s1[0..i-1] and s2[0..j-1] equal.

Approach

We will use an iterative bottom-up DP table of size (len(s1) + 1) x (len(s2) + 1).

  1. Initialization: Create a 2D array initialized to infinity or handle base cases where one string is empty.

    • dp[0][j] represents the cost when s1 is effectively empty, meaning we must delete all characters of s2[:j]. This equals sum of ASCII values for that prefix.
    • Similarly, dp[i][0] handles deleting all chars from s1.
  2. Iteration: Loop through each character index i (for s1) and j (for s2).

  3. Transition Logic:

    • If s1[i-1] == s2[j-1]: No deletion needed for this pair. Cost is same as previous diagonal: dp[i][j] = dp[i-1][j-1].
    • Else (mismatch): We must delete one character from either string to proceed towards a match or empty state.
      • Option 1: Delete char from s1: Cost is dp[i-1][j] + ord(s1[i])
      • Option 2: Delete char from s2: Cost is dp[i][j-1] + ord(s2[j])
      • Take the minimum of these two.
  4. Result: The value at dp[len(s1)][len(s2)].

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n), where mm and nn are lengths of s1 and s2. We visit each cell in the DP table once. With max length 1000, operations ≈106\approx 10^6, well within time limits for Python (typically allowing ~1-5 seconds).
  • Space Complexity: O(m×n)O(m \times n) to store the full DP table. This can be optimized to O(min⁡(m,n))O(\min(m, n)) by only keeping two rows at a time if memory is tight, but given constraints (N=1000N=1000, ≈4MB\approx 4MB for int array), standard space usage is acceptable and clearer for explanation.

Solution

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        
        # dp[i][j] stores the min ASCII delete sum to make 
        # s1[:i] and s2[:j] equal.
        # Dimensions are (m+1) x (n+1).
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Initialize first row: deleting all chars from s2 to match empty s1
        current_sum_s2 = sum(ord(c) for c in s2)
        
        # We can initialize the whole column/row logic inside loop or pre-fill.
        # Pre-filling is cleaner but let's do it via loops for clarity of recurrence.
        # Actually, simpler to fill base cases first:
        dp[0][j] = current_sum_s2  # Wait, this needs prefix sum
        
        # Let's refine initialization logic inside the loop or pre-calc row/col sums?
        # Standard way: Initialize col 0 and row 0 with cumulative ASCII sums.
        
        for i in range(m + 1):
            dp[i][0] = sum(ord(c) for c in s1[:i]) if i > 0 else 0
            
        current_sum_s2_prefix = [] # Not needed, just iterate
        
        # Re-calculate row 0 properly: cost to delete all of s2[0..j-1]
        dp[0][0] = 0
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])

        # Re-calculate col 0 properly: cost to delete all of s1[0..i-1]
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])

        # Fill the rest of the table
        for i in range(1, m + 1):
            char_s1 = s1[i - 1]
            cost_char_s1 = ord(char_s1)
            
            for j in range(1, n + 1):
                char_s2 = s2[j - 1]
                
                if char_s1 == char_s2:
                    # Characters match, no deletion needed for this pair. 
                    # Cost is inherited from the diagonal state (both prefixes reduced by one).
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    # Mismatch: choose min cost between deleting s1's char or s2's char
                    delete_from_s1 = dp[i - 1][j] + cost_char_s1
                    delete_from_s2 = dp[i][j - 1] + ord(char_s2)
                    
                    dp[i][j] = min(delete_from_s1, delete_from_s2)

        return dp[m][n]

Edge Cases Handled

  • Empty Strings: The initialization loops handle i=0 and j=0. If input is empty strings or one string becomes effectively “deleted” (empty), the cumulative sum logic correctly returns 0 cost for matching empties.
  • No Common Characters: Logic naturally accumulates full ASCII sums of both strings in diagonal/edge cases if no matches occur, resulting in deleting everything from both.
  • Identical Strings: The if char_s1 == char_s2 branch ensures we propagate 0 cost along the main diagonal for matching characters without adding deletion costs.