Minimum ASCII Delete Sum for Two Strings
MedPrompt
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 <= 1000s1ands2consist of lowercase English letters.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive method to solve the problem. The core idea is to explore all possible ways of deleting characters from both strings to make them equal and find the one with the minimum ASCII sum of deleted characters. At each pair of characters (s1[i], s2[j]), we make a decision: if they are equal, we keep them and move on; if they are not, we must delete one of them and recursively calculate the minimum cost for the rest of the strings.
Algorithm
- Define a recursive function, let's call it
findMinSum(s1, s2, i, j), which computes the minimum ASCII delete sum for the suffixess1[i:]ands2[j:]. - Base Cases:
- If both
iandjhave reached the end of their respective strings, it means we have successfully matched them. The cost is 0. - If only
ihas reached the end ofs1, we must delete all remaining characters ins2from indexjonwards. The cost is the sum of ASCII values ofs2[j:]. - If only
jhas reached the end ofs2, we must delete all remaining characters ins1from indexionwards. The cost is the sum of ASCII values ofs1[i:].
- If both
- Recursive Step:
- If
s1.charAt(i) == s2.charAt(j), the characters match. We don't need to delete them. We move to the next characters in both strings. The cost isfindMinSum(s1, s2, i + 1, j + 1). - If
s1.charAt(i) != s2.charAt(j), we have two choices: a. Deletes1.charAt(i)and find the minimum sum fors1[i+1:]ands2[j:]. The cost iss1.charAt(i) + findMinSum(s1, s2, i + 1, j). b. Deletes2.charAt(j)and find the minimum sum fors1[i:]ands2[j+1:]. The cost iss2.charAt(j) + findMinSum(s1, s2, i, j + 1). We take the minimum of these two options.
- If
- The initial call to the function will be
findMinSum(s1, s2, 0, 0).
Walkthrough
The function findMinSum(i, j) calculates the minimum deletion cost for substrings s1.substring(i) and s2.substring(j). If the characters s1.charAt(i) and s2.charAt(j) are the same, we don't need to delete them, so we recursively call findMinSum(i + 1, j + 1). If they differ, we have two choices: either delete s1.charAt(i) and solve for s1.substring(i+1) and s2.substring(j), or delete s2.charAt(j) and solve for s1.substring(i) and s2.substring(j+1). We choose the option that results in a smaller total deletion sum. The base cases handle situations where one or both strings are exhausted.
public class Solution { public int minimumDeleteSum(String s1, String s2) { return findMinSum(s1, s2, 0, 0); } private int findMinSum(String s1, String s2, int i, int j) { // Base case: If both strings are empty, no more deletions are needed. if (i == s1.length() && j == s2.length()) { return 0; } // Base case: If s1 is empty, delete remaining characters of s2. if (i == s1.length()) { int deleteCost = 0; for (int k = j; k < s2.length(); k++) { deleteCost += s2.charAt(k); } return deleteCost; } // Base case: If s2 is empty, delete remaining characters of s1. if (j == s2.length()) { int deleteCost = 0; for (int k = i; k < s1.length(); k++) { deleteCost += s1.charAt(k); } return deleteCost; } // If characters are the same, no deletion is needed for these characters. if (s1.charAt(i) == s2.charAt(j)) { return findMinSum(s1, s2, i + 1, j + 1); } else { // If characters are different, we have two choices: // 1. Delete character from s1. int deleteS1 = s1.charAt(i) + findMinSum(s1, s2, i + 1, j); // 2. Delete character from s2. int deleteS2 = s2.charAt(j) + findMinSum(s1, s2, i, j + 1); return Math.min(deleteS1, deleteS2); } }}Complexity
Time
O(2^(m+n)), where m and n are the lengths of s1 and s2. In the worst case (no matching characters), each call branches into two, leading to an exponential number of calls.
Space
O(m + n), where m and n are the lengths of s1 and s2. This space is used by the recursion stack.
Trade-offs
Pros
Simple to conceptualize and follows the problem definition directly.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
The brute-force recursive solution suffers from re-calculating the same subproblems multiple times. We can optimize this by using memoization, a technique also known as top-down dynamic programming. We store the result of each subproblem (i, j) in a cache or a 2D array. When the function is called again with the same i and j, we can directly return the stored result instead of re-computing it, effectively pruning the recursion tree.
Algorithm
- The recursive structure is the same as the brute-force approach.
- We introduce a 2D array,
memo[m][n], to store the results of subproblems.memo[i][j]will store the result offindMinSum(i, j). - Initialize the
memotable with a special value (e.g., -1) to indicate that a subproblem has not been solved yet. - In the recursive function, before any computation, check if
memo[i][j]already has a computed value. If it does, return the stored value immediately. - If the value is not in the memo table, compute it using the same recursive logic as the brute-force approach.
- Before returning the computed result, store it in
memo[i][j]for future use. - The initial call remains
findMinSum(s1, s2, 0, 0).
Walkthrough
We augment the recursive function with a 2D integer array memo of size s1.length() x s2.length(). Each cell memo[i][j] stores the minimum delete sum for s1[i:] and s2[j:]. Initially, all cells of memo are filled with a sentinel value like -1. When findMinSum(i, j) is called, it first checks memo[i][j]. If it's not -1, the value is returned. Otherwise, the result is computed recursively, stored in memo[i][j], and then returned. This ensures that each state (i, j) is computed only once.
public class Solution { private Integer[][] memo; public int minimumDeleteSum(String s1, String s2) { memo = new Integer[s1.length()][s2.length()]; return findMinSum(s1, s2, 0, 0); } private int findMinSum(String s1, String s2, int i, int j) { if (i == s1.length() && j == s2.length()) { return 0; } if (i == s1.length()) { int deleteCost = 0; for (int k = j; k < s2.length(); k++) { deleteCost += s2.charAt(k); } return deleteCost; } if (j == s2.length()) { int deleteCost = 0; for (int k = i; k < s1.length(); k++) { deleteCost += s1.charAt(k); } return deleteCost; } if (memo[i][j] != null) { return memo[i][j]; } int result; if (s1.charAt(i) == s2.charAt(j)) { result = findMinSum(s1, s2, i + 1, j + 1); } else { int deleteS1 = s1.charAt(i) + findMinSum(s1, s2, i + 1, j); int deleteS2 = s2.charAt(j) + findMinSum(s1, s2, i, j + 1); result = Math.min(deleteS1, deleteS2); } memo[i][j] = result; return result; }}Complexity
Time
O(m * n), where m and n are the lengths of s1 and s2. Each subproblem `(i, j)` is computed only once.
Space
O(m * n) for the memoization table, plus O(m + n) for the recursion stack. The total space is dominated by the table, so it's O(m * n).
Trade-offs
Pros
Drastically improves time complexity from exponential to polynomial.
Guaranteed to find the optimal solution within the time limits for the given constraints.
The logic closely follows the recursive thought process, making it relatively easy to transition from the brute-force solution.
Cons
Uses O(m*n) space for the memoization table, which can be large.
May cause a StackOverflowError for very large inputs due to deep recursion, although the given constraints (lengths up to 1000) are usually manageable.
This approach, also known as tabulation or bottom-up dynamic programming, solves the problem iteratively. It avoids recursion and builds the solution from the smallest subproblems up to the final problem. We use a 2D array, dp, where dp[i][j] represents the minimum ASCII delete sum required to make the prefixes s1.substring(0, i) and s2.substring(0, j) equal. By filling this table systematically, we can find the solution for the full strings.
Algorithm
- Create a 2D DP table,
dp, of size(m+1) x (n+1), wheredp[i][j]will store the minimum ASCII delete sum to makes1[0...i-1]ands2[0...j-1]equal. - Initialization (Base Cases):
dp[0][0] = 0(making two empty strings equal costs 0).- Fill the first row:
dp[0][j]is the cost of making an empty string ands2[0...j-1]equal, which requires deleting all characters of thes2prefix. So,dp[0][j] = dp[0][j-1] + s2.charAt(j-1). - Fill the first column:
dp[i][0]is the cost of makings1[0...i-1]and an empty string equal. So,dp[i][0] = dp[i-1][0] + s1.charAt(i-1).
- Fill the rest of the table: Iterate with
ifrom 1 tomandjfrom 1 ton.- If
s1.charAt(i-1) == s2.charAt(j-1), the last characters match. No deletion is needed for them. The cost is inherited from the subproblem without these characters:dp[i][j] = dp[i-1][j-1]. - If
s1.charAt(i-1) != s2.charAt(j-1), we must delete one of them. We take the minimum of two choices: a. Deletes1.charAt(i-1):dp[i-1][j] + s1.charAt(i-1). b. Deletes2.charAt(j-1):dp[i][j-1] + s2.charAt(j-1). So,dp[i][j] = Math.min(dp[i-1][j] + s1.charAt(i-1), dp[i][j-1] + s2.charAt(j-1)).
- If
- Result: The final answer is in
dp[m][n], which represents the minimum delete sum for the entires1ands2.
Walkthrough
We build a (m+1) x (n+1) table. The first row and column are initialized to handle the base cases where one of the strings is empty. For any cell dp[i][j], we look at the characters s1.charAt(i-1) and s2.charAt(j-1). If they are equal, the cost dp[i][j] is the same as dp[i-1][j-1]. If they are different, we must incur a deletion cost. The minimum cost is either by deleting s1.charAt(i-1) (cost dp[i-1][j] + s1.charAt(i-1)) or by deleting s2.charAt(j-1) (cost dp[i][j-1] + s2.charAt(j-1)). We fill the table row by row, and the value in the bottom-right cell, dp[m][n], gives the final answer.
public class Solution { public int minimumDeleteSum(String s1, String s2) { int m = s1.length(); int n = s2.length(); int[][] dp = new int[m + 1][n + 1]; // Initialize first column for (int i = 1; i <= m; i++) { dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1); } // Initialize first row for (int j = 1; j <= n; j++) { dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1); } // Fill the rest of the table 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 { int deleteS1 = dp[i - 1][j] + s1.charAt(i - 1); int deleteS2 = dp[i][j - 1] + s2.charAt(j - 1); dp[i][j] = Math.min(deleteS1, deleteS2); } } } return dp[m][n]; }}Complexity
Time
O(m * n) due to the nested loops iterating through all cells of the DP table.
Space
O(m * n) for the 2D DP table.
Trade-offs
Pros
Avoids recursion overhead and the risk of stack overflow.
Often slightly faster in practice than the memoized recursive version due to better cache locality and no function call overhead.
The logic is systematic and easy to follow.
Cons
Requires O(m*n) space, which might be a concern for very large constraints, although it's acceptable for this problem.
This is the most efficient approach in terms of space. By analyzing the state transitions of the bottom-up DP, we notice that calculating dp[i][j] only requires values from the current row (dp[i][j-1]) and the previous row (dp[i-1][j] and dp[i-1][j-1]). This dependency allows us to discard rows that are no longer needed, reducing the space complexity from O(m*n) to O(n) (or O(min(m, n))). We can achieve this by using a single 1D array to represent the current row being computed, while cleverly storing the necessary values from the previous row.
Algorithm
- Observe that to compute the current row
iof the DP table, we only need values from the previous rowi-1. - We can optimize space by using only a 1D array,
dp, of sizen+1, wherenis the length of the shorter string (to minimize space usage). - Let's assume
s2is the shorter string. Initialize thedparray to represent the first row of the 2D table:dp[j]will be the sum of ASCII values ofs2[0...j-1]. - Iterate through
s1fromi = 1tom. In each iteration, we will compute the values for the current row. - Inside the loop for
i, we need to maintain the value ofdp[i-1][j-1](the 'top-left' cell). Let's use a variableprev_row_j_minus_1for this. - For each
i, first updatedp[0](the first column value). Then, loop throughjfrom 1 ton:- Store the current
dp[j](which isdp[i-1][j]) in a temporary variabletempbefore it gets overwritten. - Calculate the new
dp[j](which isdp[i][j]) usingprev_row_j_minus_1(for thedp[i-1][j-1]term) and the just-updateddp[j-1](for thedp[i][j-1]term). - Update
prev_row_j_minus_1totempfor the nextj's iteration.
- Store the current
- After the loops complete,
dp[n]will hold the final answer.
Walkthrough
We use a 1D array dp of size n+1. This array will store the values of one row of our conceptual 2D DP table. We iterate through s1 character by character, and for each character, we update the dp array to compute the next row. A key detail is that when computing the new dp[j], we need the old dp[j] (from the previous row) and the old dp[j-1] (also from the previous row). Since dp[j-1] is updated before dp[j], we need an extra variable, prev_row_j_minus_1, to hold the value of dp[i-1][j-1] before it's overwritten.
public class Solution { public int minimumDeleteSum(String s1, String s2) { int m = s1.length(); int n = s2.length(); // Ensure s2 is the shorter string to optimize space if (m < n) { return minimumDeleteSum(s2, s1); } int[] dp = new int[n + 1]; // Initialize first row for (int j = 1; j <= n; j++) { dp[j] = dp[j - 1] + s2.charAt(j - 1); } // Fill the table row by row for (int i = 1; i <= m; i++) { int prev_row_j_minus_1 = dp[0]; // This is dp[i-1][j-1] for j=1 dp[0] += s1.charAt(i - 1); // Update first column value for current row for (int j = 1; j <= n; j++) { int temp = dp[j]; // This is dp[i-1][j] if (s1.charAt(i - 1) == s2.charAt(j - 1)) { dp[j] = prev_row_j_minus_1; } else { // dp[j] is old dp[i-1][j], dp[j-1] is new dp[i][j-1] dp[j] = Math.min(dp[j] + s1.charAt(i - 1), dp[j - 1] + s2.charAt(j - 1)); } prev_row_j_minus_1 = temp; } } return dp[n]; }}Complexity
Time
O(m * n), as we still need to compute the value for each of the m*n states.
Space
O(min(m, n)). We use a 1D array whose size is proportional to the length of the shorter string.
Trade-offs
Pros
Most space-efficient solution.
Maintains the optimal O(m*n) time complexity.
Cons
The logic is slightly more complex to implement correctly compared to the 2D DP approach, as it requires careful management of state within a single array.
Solutions
Solution
class Solution {public int minimumDeleteSum(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] f = new int[m + 1][n + 1]; for (int i = 1; i <= m; ++i) { f[i][0] = f[i - 1][0] + s1.charAt(i - 1); } for (int j = 1; j <= n; ++j) { f[0][j] = f[0][j - 1] + 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)) { f[i][j] = f[i - 1][j - 1]; } else { f[i][j] = Math.min(f[i - 1][j] + s1.charAt(i - 1), f[i][j - 1] + s2.charAt(j - 1)); } } } return f[m][n]; }}/** * @param {string} s1 * @param {string} s2 * @return {number} */ var minimumDeleteSum = function ( s1 , s2 ) { const m = s1 . length ; const n = s2 . length ; const f = Array . from ({ length : m + 1 }, () => Array ( n + 1 ). fill ( 0 )); for ( let i = 1 ; i <= m ; ++ i ) { f [ i ][ 0 ] = f [ i - 1 ][ 0 ] + s1 [ i - 1 ]. charCodeAt ( 0 ); } for ( let j = 1 ; j <= n ; ++ j ) { f [ 0 ][ j ] = f [ 0 ][ j - 1 ] + s2 [ j - 1 ]. charCodeAt ( 0 ); } for ( let i = 1 ; i <= m ; ++ i ) { for ( let j = 1 ; j <= n ; ++ j ) { if ( s1 [ i - 1 ] === s2 [ j - 1 ]) { f [ i ][ j ] = f [ i - 1 ][ j - 1 ]; } else { f [ i ][ j ] = Math . min ( f [ i - 1 ][ j ] + s1 [ i - 1 ]. charCodeAt ( 0 ), f [ i ][ j - 1 ] + s2 [ j - 1 ]. charCodeAt ( 0 ), ); } } } return f [ m ][ n ]; };class Solution {public: int minimumDeleteSum(string s1, string s2) { int m = s1.size(), n = s2.size(); int f[m + 1][n + 1]; memset(f, 0, sizeof f); for (int i = 1; i <= m; ++i) { f[i][0] = f[i - 1][0] + s1[i - 1]; } for (int j = 1; j <= n; ++j) { f[0][j] = f[0][j - 1] + s2[j - 1]; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (s1[i - 1] == s2[j - 1]) { f[i][j] = f[i - 1][j - 1]; } else { f[i][j] = min(f[i - 1][j] + s1[i - 1], f[i][j - 1] + s2[j - 1]); } } } return f[m][n]; }};class Solution: def minimumDeleteSum(self, s1: str, s2: str) -> int: m, n = len(s1), len(s2) f = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): f[i][0] = f[i - 1][0] + ord(s1[i - 1]) for j in range(1, n + 1): f[0][j] = f[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]: f[i][j] = f[i - 1][j - 1] else: f[i][j] = min(f[i - 1][j] + ord(s1[i - 1]), f[i][j - 1] + ord(s2[j - 1])) return f[m][n]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.