algoadvance

The problem is to find the minimum ASCII delete sum for two strings s1 and s2. The ASCII delete sum is the sum of the ASCII values of deleted characters to make the two strings equal.

Here’s the problem stated more formally:

• Given two strings s1 and s2, return the minimum ASCII delete sum of making s1 and s2 equal.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the strings s1 and s2?
     • Typically, for these problems, the strings can be up to 1000 characters long.
   • Are the strings composed only of lowercase English letters, or can they include other characters?
     • Assume the strings are composed of lowercase English letters.
2. Output Format:
   • Should the function return an integer representing the minimum ASCII delete sum?

Strategy

This is a classic dynamic programming problem where we need to minimize the total ASCII values deleted to make s1 and s2 equal. Here is the step-by-step strategy to solve this problem:

1. Define a DP Table:
   • Create a 2D DP table dp where dp[i][j] represents the minimum ASCII delete sum to make s1[:i] and s2[:j] equal.
2. Initialization:
   • dp[0][0] = 0: Deleting both empty prefixes results in zero cost.
   • For the first row and column, if one of the strings is empty, the cost is the ASCII sum of the other string up to that point.
3. State Transition:
   • If the characters s1[i-1] and s2[j-1] are the same, dp[i][j] = dp[i-1][j-1] since no deletion is needed.
   • Otherwise, take the minimum of deleting the character from s1 or s2: dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).
4. Return the Result:
   • The value in dp[m][n] gives the minimum ASCII delete sum for s1 and s2.

Code

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    
    # Initialize DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initializing 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])
    
    # Fill 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]

Time Complexity

• Time Complexity: O(m * n)
  • Here m and n are the lengths of strings s1 and s2, respectively. We fill up a 2D DP table of dimensions (m+1) x (n+1).
• Space Complexity: O(m * n)
  • The space complexity is also O(m * n) due to the storage required for the 2D DP table.

By following this approach, we can efficiently determine the minimum ASCII delete sum to make the two strings equal.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?