{x}
blog image

Minimum ASCII Delete Sum for Two Strings

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

 

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

 

Constraints:

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of lowercase English letters.

Minimum ASCII Delete Sum for Two Strings

This problem asks to find the minimum ASCII sum of deleted characters to make two strings equal. We can solve this using dynamic programming.

Approach

Let s1 and s2 be the two input strings. We can build a 2D DP table dp where dp[i][j] represents the minimum ASCII sum to make s1[0...i-1] and s2[0...j-1] equal.

  • Base Cases:

    • dp[i][0] (for i > 0): The minimum sum to make s1[0...i-1] equal to an empty string is the sum of ASCII values of characters in s1[0...i-1].
    • dp[0][j] (for j > 0): Similarly, the minimum sum to make an empty string equal to s2[0...j-1] is the sum of ASCII values of characters in s2[0...j-1].
    • dp[0][0] = 0

  • Recursive Relation:

    • If s1[i-1] == s2[j-1], it means these characters are already equal, so we don't need to delete them. dp[i][j] = dp[i-1][j-1].
    • If s1[i-1] != s2[j-1], we have two choices:
      • Delete s1[i-1]: dp[i][j] = dp[i-1][j] + ASCII(s1[i-1])
      • Delete s2[j-1]: dp[i][j] = dp[i][j-1] + ASCII(s2[j-1]) We choose the minimum of these two options.

  • Result: The final answer is dp[m][n], where m and n are the lengths of s1 and s2 respectively.

Time and Space Complexity

  • Time Complexity: O(m*n), where m and n are the lengths of the two strings. This is because we iterate through the entire DP table.
  • Space Complexity: O(m*n) to store the DP table. We could potentially optimize this to O(min(m,n)) by using only two rows of the DP table, but for clarity, the provided solutions use the full table.

Code Implementation (Python)

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    # Base cases
    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])
 
    # Recursive relation
    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]

The code implementations in other languages (Java, C++, Go, TypeScript, Javascript) follow the same algorithm and logic, differing only in syntax and data structure specifics. They all have the same time and space complexity.