We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum ASCII Delete Sum for Two Strings

Difficulty: Medium

Problem Description

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

Key Insights

  • The goal is to make two strings equal by deleting characters.
  • The ASCII values of the characters that are deleted contribute to the total sum.
  • A dynamic programming approach can be used to efficiently calculate the minimum sum of deleted ASCII values.
  • The problem can be viewed as finding the longest common subsequence (LCS), where the characters not in the LCS are the ones that need to be deleted.

Space and Time Complexity

Time Complexity: O(m * n), where m is the length of s1 and n is the length of s2.
Space Complexity: O(m * n) for the dynamic programming table.

Solution

We can solve this problem using dynamic programming. We will create a 2D array, dp, where dp[i][j] will store the minimum ASCII delete sum needed to make the first i characters of s1 and the first j characters of s2 equal.

  1. Initialize the dp array with size (m+1) x (n+1), where m and n are the lengths of s1 and s2, respectively.
  2. Fill the first row and first column to represent the cost of deleting characters from either string.
  3. Iterate through each character pair from both strings:
    • If the characters match, carry forward the previous cost (no deletion needed).
    • If they don't match, calculate the cost of deleting either character and take the minimum.
  4. The final answer will be found in dp[m][n].

Code Solutions

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the first row and column
    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])
    
    # Fill the dp table
    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]
← Back to All Questions