Code Implementation

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

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i)
            dp[i][0] = dp[i-1][0] + (int)s1[i-1];
        for (int j = 1; j <= n; ++j)
            dp[0][j] = dp[0][j-1] + (int)s2[j-1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(
                        dp[i-1][j] + (int)s1[i-1], 
                        dp[i][j-1] + (int)s2[j-1]
                    );
            }
        }
        return dp[m][n];
    }
};
      

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            dp[i][0] = dp[i-1][0] + (int)s1.charAt(i-1);
        for (int j = 1; j <= n; j++)
            dp[0][j] = dp[0][j-1] + (int)s2.charAt(j-1);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = Math.min(
                        dp[i-1][j] + (int)s1.charAt(i-1), 
                        dp[i][j-1] + (int)s2.charAt(j-1)
                    );
            }
        }
        return dp[m][n];
    }
}
      

var minimumDeleteSum = function(s1, s2) {
    const m = s1.length, n = s2.length;
    const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for (let i = 1; i <= m; i++)
        dp[i][0] = dp[i-1][0] + s1.charCodeAt(i-1);
    for (let j = 1; j <= n; j++)
        dp[0][j] = dp[0][j-1] + s2.charCodeAt(j-1);
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s1[i-1] === s2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = Math.min(
                    dp[i-1][j] + s1.charCodeAt(i-1),
                    dp[i][j-1] + s2.charCodeAt(j-1)
                );
        }
    }
    return dp[m][n];
};
      

Problem Description

You are given two strings, s1 and s2. Your task is to make the two strings equal by deleting some characters from either string. The cost of deleting a character is equal to its ASCII value. You need to find the minimum total ASCII sum of deleted characters to make s1 and s2 equal.

• Each character can be deleted from either s1 or s2, but not both at the same time.
• You can delete any number of characters (including zero).
• There is always at least one way to make the strings equal (by deleting all characters).
• Return the minimum possible sum of ASCII values of deleted characters.

Thought Process

The problem asks us to make two strings equal by deleting characters, with the cost being the sum of their ASCII values. At first glance, you might consider trying all possible ways to delete characters, but this would be extremely inefficient, especially for longer strings.

Instead, we can relate this problem to the concept of the Longest Common Subsequence (LCS). If we keep the LCS of both strings, the only characters we need to delete are those not in the LCS. The minimum cost, therefore, comes from deleting all characters not shared in the LCS.

However, rather than just finding the LCS, we need to track the cost of deletions. This leads us to dynamic programming, where we can build up the solution by considering prefixes of s1 and s2, and using previously computed results to make optimal choices at each step.

Solution Approach

• Dynamic Programming Table:
  • Let dp[i][j] represent the minimum ASCII delete sum to make s1[0..i-1] and s2[0..j-1] equal.
• Initialization:
  • If one string is empty, the cost is the sum of ASCII values of all characters in the other string (since we must delete all of them).
• Recurrence Relation:
  • If s1[i-1] == s2[j-1], no deletion is needed for these characters: dp[i][j] = dp[i-1][j-1].
  • Otherwise, we have two choices:
    • Delete s1[i-1]: cost is dp[i-1][j] + ord(s1[i-1])
    • Delete s2[j-1]: cost is dp[i][j-1] + ord(s2[j-1])
    We take the minimum of these two options.
• Final Answer:
  • The answer is dp[m][n], where m and n are the lengths of s1 and s2 respectively.
• Why Dynamic Programming?
  • DP avoids recalculating subproblems and ensures that each prefix combination is only computed once, resulting in efficient performance.

Example Walkthrough

Let's use s1 = "sea" and s2 = "eat" as an example.

1. Initialize the DP table:
   • First row and column are filled with cumulative ASCII sums (since one string is empty).
2. Compare characters:
   • s1[0] = 's' vs s2[0] = 'e': not equal. Options:
     • Delete 's' (cost 115) or delete 'e' (cost 101). Choose minimum.
   • s1[1] = 'e' vs s2[0] = 'e': equal. No deletion needed; inherit value from dp[0][0].
   • Continue filling the table for all characters.
3. Final cell dp[3][3] gives the minimum ASCII delete sum, which is 231 (delete 's' from s1 and 't' from s2).

This step-by-step process ensures we always make the optimal (minimum cost) choice at each character comparison.

Time and Space Complexity

• Brute-force Approach:
  • Would try all possible deletions, resulting in exponential time (O(2^m+n)), which is infeasible for long strings.
• Dynamic Programming Approach:
  • Time Complexity: O(m*n), where m and n are the lengths of s1 and s2, since we fill an m x n table.
  • Space Complexity: O(m*n) for the DP table. This can be reduced to O(min(m, n)) with optimization, but the standard solution uses the full table.

Summary

The Minimum ASCII Delete Sum for Two Strings problem is elegantly solved with dynamic programming by breaking the problem into manageable subproblems. By considering the cost of deleting each character and building up a solution from smaller prefixes, we ensure an optimal and efficient approach. This technique avoids redundant calculations and leverages the overlapping subproblem structure, making it both robust and scalable for larger inputs.