LeetCode Solutions Blog

Minimum ASCII Delete Sum for Two Strings

Number: 712

Difficulty: Medium

Paid? No

Problem Description

Given two strings s1 and s2, the goal is to delete characters from both strings to make them equal while minimizing the total cost. The cost is the sum of the ASCII values of the characters deleted.

Key Insights

Use dynamic programming to systematically compare characters of both strings.
Define a state dp[i][j] representing the minimum deletion cost for the substrings s1[i:] and s2[j:].
If s1[i] equals s2[j], no cost is incurred and we move diagonally.
If the characters differ, decide between deleting s1[i] or s2[j] and take the minimum cost.
Base cases handle situations where one string is empty by summing the ASCII values of the remaining characters in the other string.

Space and Time Complexity

Time Complexity: O(n * m), where n and m are the lengths of s1 and s2. Space Complexity: O(n * m), due to the DP table used to store intermediate results.

Solution

We build a 2D DP table where dp[i][j] is the minimum ASCII deletion sum required for making the substrings s1[i:] and s2[j:] equal. Starting from the end of the strings, if characters match then carry over the cost from dp[i+1][j+1]. Otherwise, consider the cost of deleting the current character from s1 or s2, and update dp[i][j] accordingly with the minimum of these two possibilities. The final answer is stored in dp[0][0].

Code Solutions

# Python implementation with line-by-line comments

def minimumDeleteSum(s1: str, s2: str) -> int:
    n, m = len(s1), len(s2)
    # Initialize a DP table with dimensions (n+1) x (m+1) filled with 0's
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # Base case: when s2 is empty, delete all remaining characters of s1
    for i in range(n - 1, -1, -1):
        dp[i][m] = dp[i + 1][m] + ord(s1[i])
    
    # Base case: when s1 is empty, delete all remaining characters of s2
    for j in range(m - 1, -1, -1):
        dp[n][j] = dp[n][j + 1] + ord(s2[j])
    
    # Fill the DP table from the bottom right corner up
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            # If characters are the same, no deletion cost is needed
            if s1[i] == s2[j]:
                dp[i][j] = dp[i + 1][j + 1]
            else:
                # Otherwise, try deleting either s1[i] or s2[j] and take the minimum cost
                dp[i][j] = min(
                    dp[i + 1][j] + ord(s1[i]),  # Delete character s1[i]
                    dp[i][j + 1] + ord(s2[j])   # Delete character s2[j]
                )
    # Return the minimum cost to make the entire strings equal
    return dp[0][0]

# Example usage:
print(minimumDeleteSum("sea", "eat"))  # Expected output: 231