Minimum ASCII Delete Sum for Two Strings - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given two strings s1 and s2. Delete characters from either string so both become equal while minimizing the total ASCII value of deleted characters. The goal is not the number of deletions but the minimum sum of ASCII values removed.
Approach 1: Recursion with Memoization (Time: O(m*n), Space: O(m*n))
This approach models the problem as a recursive comparison of suffixes from both strings. At position i in s1 and j in s2, you either keep the characters if they match or delete one of them. If s1[i] == s2[j], move both pointers forward with no cost. Otherwise, try deleting s1[i] or s2[j] and add their ASCII values to the total cost. Store results for each state (i, j) in a memo table to avoid recomputation. Without memoization the recursion becomes exponential; caching reduces it to O(m*n). This approach clearly exposes the decision process and is useful when reasoning about overlapping subproblems in dynamic programming.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(m*n), Space: O(m*n))
The iterative DP solution builds a table dp[i][j] representing the minimum ASCII delete sum required to make s1[i:] and s2[j:] equal. Initialize the last row and column by deleting all remaining characters from the other string, accumulating ASCII values. Then iterate backward through both strings. If characters match, copy the value from dp[i+1][j+1]. If they differ, compute the minimum between deleting from s1 (ASCII(s1[i]) + dp[i+1][j]) or deleting from s2 (ASCII(s2[j]) + dp[i][j+1]). The final answer is dp[0][0]. This formulation is similar to the weighted version of the longest common subsequence problem and relies heavily on string comparison and dynamic programming state transitions.
The DP interpretation can also be viewed as maximizing the ASCII value of the common subsequence shared by both strings. Instead of explicitly building the subsequence, the algorithm directly computes the minimum cost of deletions. The bottom-up version avoids recursion overhead and is usually the most predictable implementation in interviews and production code.
Recommended for interviews: The bottom-up dynamic programming approach is the expected solution. It demonstrates clear state definition (dp[i][j]), correct transitions, and optimal O(m*n) complexity. Starting with the recursive memoized version shows understanding of the subproblem structure, but converting it into an iterative DP table signals stronger problem-solving maturity.
Approach 1: Dynamic Programming Approach
This approach involves using a 2D table to compute the minimum ASCII delete sum to make the two strings equal. The table is filled using a bottom-up dynamic programming method, considering the cost of deleting characters from either string.
For each index pair (i, j), we decide whether to delete a character from either s1 or s2 or take the sum from previously computed states to minimize the ASCII sum deletion cost.
This solution defines a 2D DP table where dp[i][j] represents the minimum ASCII delete sum to make the substrings s1[i:] and s2[j:] equal. We pre-compute the additional cost of deleting each character from the end of the strings and use these results to fill the DP table iteratively. If characters at positions i and j are equal, we take the diagonal value; otherwise, we take the minimum cost of deleting either character.
Complexity
Time Complexity: O(m * n), where m and n are the lengths of s1 and s2. This is because we need to fill the entire DP table.
Space Complexity: O(m * n), due to storage in a 2D table.
Approach 2: Recursion with Memoization
This approach uses a recursive function with memoization to solve the problem. The recursive function computes the minimum ASCII sum by exploring all possible deletions and storing intermediate results to avoid redundant calculations. This can be a more intuitive approach for those familiar with recursion at the expense of higher time complexity when not optimized with memoization.
In this solution, we use a memoization dictionary to save results of previous calculations to avoid recomputation. The recursive helper function attempts deletions from s1 or s2 whenever theres is no character match, storing and reusing the computed results to find the minimum ASCII delete sum.
Code
C#
JavaScript
C
Complexity
Time Complexity: O(m * n) due to memoization reducing the duplicate calculations.
Space Complexity: O(m * n), with space used for the recursion stack and memoization storage.
Approach 3: Dynamic Programming
We define f[i][j] as the minimum sum of ASCII values of deleted characters required to make the first i characters of s_1 equal to the first j characters of s_2. The answer is f[m][n].
If s_1[i-1] = s_2[j-1], then f[i][j] = f[i-1][j-1]. Otherwise, we can delete either s_1[i-1] or s_2[j-1] to minimize f[i][j]. Therefore, the state transition equation is as follows:
$
f[i][j]=
\begin{cases}
f[i-1][j-1], & s_1[i-1] = s_2[j-1] \
min(f[i-1][j] + s_1[i-1], f[i][j-1] + s_2[j-1]), & s_1[i-1] neq s_2[j-1]
\end{cases}
The initial state is f[0][j] = f[0][j-1] + s_2[j-1], f[i][0] = f[i-1][0] + s_1[i-1].
Finally, return f[m][n].
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the lengths of s_1 and s_2$ respectively.
Similar problems:
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n), where m and n are the lengths of s1 and s2. This is because we need to fill the entire DP table. |
| Recursion with Memoization | Time Complexity: O(m * n) due to memoization reducing the duplicate calculations. |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursion with Memoization | O(m*n) | O(m*n) | When you want a clear top-down representation of subproblems or to quickly convert a recursive idea into an optimized solution. |
| Dynamic Programming (Bottom-Up) | O(m*n) | O(m*n) | Preferred in interviews and production. Iterative table avoids recursion overhead and provides predictable performance. |
Video Solution
Minimum ASCII Delete Sum for Two Strings | Intuition | Similar Problems | Leetcode 712 | MIK • codestorywithMIK • 12,960 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum ASCII Delete Sum for Two Strings easy or hard?
Minimum ASCII Delete Sum for Two Strings Python/Java solution
How to solve Minimum ASCII Delete Sum for Two Strings in O(n)?
What is the best approach for Minimum ASCII Delete Sum for Two Strings?
Is Minimum ASCII Delete Sum for Two Strings asked at Google/Amazon/Meta?
What data structure is used in Minimum ASCII Delete Sum for Two Strings?
What is the time complexity of Minimum ASCII Delete Sum for Two Strings?
Ready to solve this problem?
Practice Minimum ASCII Delete Sum for Two Strings with our built-in code editor and test cases.
Practice on FleetCode