712. Minimum ASCII Delete Sum for Two Strings


Problem Description

This problem asks for the lowest ASCII sum of deleted characters to make two given strings, s1 and s2, equal. In other words, we need to find out how many and which characters we should delete (from either or both strings) so that the remaining characters of s1 and s2 will be the same, and the sum of the ASCII values of these deleted characters is as small as possible. We only need the sum, not the specific characters to delete.

Intuition

The solution to this problem involves dynamic programming, a method for solving complex problems by breaking them down into simpler subproblems. We can visualize the problem as a grid where one string (s1) forms the rows and the other string (s2) forms the columns. Each cell in the grid represents the cost (lowest ASCII sum of deleted characters) to make the substrings equal up to that point.

Here's the intuition broken down into steps:

  1. Subproblem Definition: Define f[i][j] as the minimum cost to make the first i characters of s1 and the first j characters of s2 equal.

  2. Initial Conditions: Start by filling in the base cases. If one string is empty (i or j is 0), then f[i][j] is the sum of the ASCII values of all the characters in the other string up to that point.

  3. Iterative Solution: For each character pair (from s1[i] and s2[j]), we check if the characters are equal. If they are, the cost does not increase and it's the same as the cost for f[i-1][j-1]. If they aren't, we choose the cheaper option between deleting a character from s1 or s2. This means we add the ASCII value of the character we consider deleting to the corresponding cost, and we take the minimum of both options as our new cost for f[i][j].

  4. Build Up Solution: By filling out the grid following these rules, starting from f[0][0] and going to f[m][n] where m and n are the lengths of s1 and s2 respectively, we build up to the solution.

  5. Final Answer: After the grid is entirely filled, the answer to the problem will be the value at f[m][n], as it represents the cost of making both entire strings s1 and s2 equal.

By constructing this table, we systematically consider the cost of each possible operation, ensuring that we arrive at the minimum total cost for the entire strings.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of this solution utilizes dynamic programming, which involves storing and reusing solutions to subproblems in order to build up to the solution for the whole problem. The specific data structure used here to implement dynamic programming is a 2-dimensional list (a list of lists), which acts as a table to store the minimum cost for each subproblem.

The algorithm proceeds as follows:

  1. Initialize the Table: Create a 2D list f with dimensions (m+1) x (n+1), where m and n are the lengths of s1 and s2, respectively. This table will hold the solutions to subproblems, initialized with zeros.

  2. Set Up Base Cases: Populate the first row and the first column of the table f. Each cell in the first row represents the minimum ASCII sum for making the first i characters of s1 equal to an empty s2 by deleting characters. Each cell in the first column represents the same but for s2 to an empty s1.

    1for i in range(1, m + 1):
    2    f[i][0] = f[i - 1][0] + ord(s1[i - 1])
    3for j in range(1, n + 1):
    4    f[0][j] = f[0][j - 1] + ord(s2[j - 1])
  3. Fill in the Table: Loop through each cell of the table (excluding the first row and column which are already filled) and apply the following rules to calculate f[i][j]:

    • If s1[i - 1] == s2[j - 1], set f[i][j] to f[i - 1][j - 1], since there is no need to delete any character when they are the same.
    • If s1[i - 1] != s2[j - 1], set f[i][j] to the minimum between f[i - 1][j] + ord(s1[i - 1]) and f[i][j - 1] + ord(s2[j - 1]). This represents the cost of making strings equal either by deleting the current character from s1 or s2.
    1for i in range(1, m + 1):
    2    for j in range(1, n + 1):
    3        if s1[i - 1] == s2[j - 1]:
    4            f[i][j] = f[i - 1][j - 1]
    5        else:
    6            f[i][j] = min(
    7                f[i - 1][j] + ord(s1[i - 1]),
    8                f[i][j - 1] + ord(s2[j - 1])
    9            )
  4. Extract the Final Answer: After populating the entire table, read the value f[m][n]. This cell holds the minimum ASCII sum of deleted characters to make the two strings equal.

By following this approach, the algorithm ensures that all possible deletions are considered, and the best choice is made at each step, leading to the optimal solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above. Suppose we have two strings s1 = "sea" and s2 = "eat". We want to find the lowest ASCII sum of characters that need to be deleted to make s1 and s2 equal.

  1. Initialization: We start by initializing a 2D list f with the dimensions (m+1) x (n+1). For s1 = "sea" and s2 = "eat", the grid will look like this with m=3 and n=3:

    1[ [0, 0, 0, 0],
    2  [0, 0, 0, 0],
    3  [0, 0, 0, 0],
    4  [0, 0, 0, 0] ]
  2. Set Up Base Cases: Next, we populate the first row and the first column based on the ASCII sum of the prefixes of s1 and s2:

    1[ [0, 'e', 'a', 't'],
    2  ['s', 0, 0, 0],
    3  ['e', 0, 0, 0],
    4  ['a', 0, 0, 0] ]

    After converting characters to their ASCII sums:

    1[ [0, 101, 197, 314],
    2  [115, 0, 0, 0],
    3  [115 + 101, 0, 0, 0],
    4  [115 + 101 + 97, 0, 0, 0] ]

    The fully populated base cases are:

    1[ [0, 101, 197, 314],
    2  [115, 0, 0, 0],
    3  [216, 0, 0, 0],
    4  [313, 0, 0, 0] ]
  3. Fill in the Table: Now, we loop through the rest of the cells:

    • For f[1][1]: 's' vs 'e', they are different, so we take the min between f[0][1] + ASCII('s') = 101 + 115 and f[1][0] + ASCII('e') = 115 + 101. We choose the minimum which is 216, so f[1][1] = 216.

    • For f[1][2]: 's' vs 'a', they are different, so we take the min between f[0][2] + ASCII('s') = 197 + 115 and f[1][1] + ASCII('a') = 216 + 97. We choose the minimum which is 216 + 97, so f[1][2] = 313.

    • And so on, until we fill the entire table:

    1[ [0, 101, 197, 314],
    2  [115, 216, 313, 330],
    3  [216, 115, 216, 313],
    4  [313, 216, 209, 216] ]

    The logic behind each calculation is to minimize the ASCII sum required to make the two substrings equal, considering whether we should delete a character from s1 or s2 at each step.

  4. Extract the Final Answer: The value of f[3][3] represents the minimum ASCII sum of deleted characters to make s1 and s2 equal. From the table, this value is 216. Therefore, the lowest ASCII sum of characters that need to be deleted from "sea" and "eat" to make them equal is 216.

Solution Implementation

1class Solution:
2    def minimumDeleteSum(self, s1: str, s2: str) -> int:
3        # Calculate the length of both strings
4        len_s1, len_s2 = len(s1), len(s2)
5      
6        # Initialize a 2D array to store the minimum delete sum for sub-problems
7        dp = [[0] * (len_s2 + 1) for _ in range(len_s1 + 1)]
8      
9        # Pre-fill the first column with the delete sum of s1[i:]
10        for i in range(1, len_s1 + 1):
11            dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
12      
13        # Pre-fill the first row with the delete sum of s2[j:]
14        for j in range(1, len_s2 + 1):
15            dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
16      
17        # Start filling the DP table from (1,1) to (len_s1, len_s2)
18        for i in range(1, len_s1 + 1):
19            for j in range(1, len_s2 + 1):
20                # If the current characters are equal, then no deletion is needed
21                if s1[i - 1] == s2[j - 1]:
22                    dp[i][j] = dp[i - 1][j - 1]
23                else:
24                    # Find the minimum between deleting a character from s1 or s2
25                    dp[i][j] = min(
26                        dp[i - 1][j] + ord(s1[i - 1]),  # Delete from s1
27                        dp[i][j - 1] + ord(s2[j - 1])   # Delete from s2
28                    )
29      
30        # The value at dp[len_s1][len_s2] will be the minimum delete sum for s1 and s2
31        return dp[len_s1][len_s2]
32
1class Solution {
2    public int minimumDeleteSum(String s1, String s2) {
3        // Lengths of strings s1 and s2
4        int length1 = s1.length(), length2 = s2.length();
5        // Initialize a 2D array to store the minimum delete sum
6        int[][] dp = new int[length1 + 1][length2 + 1];
7
8        // Fill in the first column with the ASCII values of characters of s1
9        for (int i = 1; i <= length1; ++i) {
10            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
11        }
12      
13        // Fill in the first row with the ASCII values of characters of s2
14        for (int j = 1; j <= length2; ++j) {
15            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
16        }
17      
18        // Calculate the minimum delete sum for each substring of s1 and s2
19        for (int i = 1; i <= length1; ++i) {
20            for (int j = 1; j <= length2; ++j) {
21                // If the current characters are the same, no need to delete, so copy the value from dp[i - 1][j - 1]
22                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
23                    dp[i][j] = dp[i - 1][j - 1];
24                } else {
25                    // If characters are different, calculate the minimum delete sum
26                    // by comparing the cost of deleting from s1 to the cost of deleting from s2
27                    dp[i][j] = Math.min(dp[i - 1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
28                }
29            }
30        }
31      
32        // The answer is in dp[length1][length2] which contains the minimum delete sum to make the strings equal
33        return dp[length1][length2];
34    }
35}
36
1#include <cstring> // for using memset
2#include <algorithm> // for using min function
3using namespace std;
4
5class Solution {
6public:
7    int minimumDeleteSum(string s1, string s2) {
8        int m = s1.size();
9        int n = s2.size();
10        // dp array to store the minimum ASCII delete sum for two substrings ending up to (i-1) in s1 and (j-1) in s2
11        int dp[m + 1][n + 1];
12        // Initializing the dp array with 0's
13        memset(dp, 0, sizeof(dp));
14      
15        // Calculate the delete sum for s1 when s2 is empty
16        for (int i = 1; i <= m; ++i) {
17            dp[i][0] = dp[i - 1][0] + s1[i - 1];
18        }
19      
20        // Calculate the delete sum for s2 when s1 is empty
21        for (int j = 1; j <= n; ++j) {
22            dp[0][j] = dp[0][j - 1] + s2[j - 1];
23        }
24      
25        // Compute dp values in a bottom-up manner
26        for (int i = 1; i <= m; ++i) {
27            for (int j = 1; j <= n; ++j) {
28                // If characters are the same, no need to delete, carry over the sum from previous subproblem
29                if (s1[i - 1] == s2[j - 1]) {
30                    dp[i][j] = dp[i - 1][j - 1];
31                } else {
32                    // Otherwise, choose the minimum sum achieved by deleting character from either s1 or s2
33                    dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
34                }
35            }
36        }
37      
38        // The final result is stored in dp[m][n], which involves the whole of s1 and s2
39        return dp[m][n];
40    }
41};
42
1function minimumDeleteSum(s1: string, s2: string): number {
2    const s1Length = s1.length;
3    const s2Length = s2.length;
4
5    // Initialize a 2D array to store the minimum delete sum dp values
6    const dp = Array.from({ length: s1Length + 1 }, () => Array(s2Length + 1).fill(0));
7  
8    // Fill out the base cases for the first row, cumulative ASCII sum of s1's prefixes
9    for (let i = 1; i <= s1Length; ++i) {
10        dp[i][0] = dp[i - 1][0] + s1.charCodeAt(i - 1);
11    }
12  
13    // Fill out the base cases for the first column, cumulative ASCII sum of s2's prefixes
14    for (let j = 1; j <= s2Length; ++j) {
15        dp[0][j] = dp[0][j - 1] + s2.charCodeAt(j - 1);
16    }
17  
18    // Dynamic programming to fill out the rest of the dp table
19    for (let i = 1; i <= s1Length; ++i) {
20        for (let j = 1; j <= s2Length; ++j) {
21            if (s1[i - 1] === s2[j - 1]) {
22                // If characters match, take the diagonal value
23                dp[i][j] = dp[i - 1][j - 1];
24            } else {
25                // Otherwise, take the minimum of deleting from s1 or s2, and add the ASCII
26                // value of the deleted character
27                dp[i][j] = Math.min(
28                    dp[i - 1][j] + s1.charCodeAt(i - 1),
29                    dp[i][j - 1] + s2.charCodeAt(j - 1),
30                );
31            }
32        }
33    }
34  
35    // The last cell of the dp table will have the answer
36    return dp[s1Length][s2Length];
37}
38

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the nested loops that iterate over the lengths of both strings s1 and s2. Since we iterate over all i from 1 to m and all j from 1 to n, where m is the length of s1 and n is the length of s2, the time complexity is O(m * n).

Space Complexity

The space complexity of the code is primarily due to the 2D list f, which has dimensions (m + 1) x (n + 1), requiring a total of (m + 1) * (n + 1) space. So, the space complexity is also O(m * n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer techniques do you use to check if a string is a palindrome?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄