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 <= 1000s1 and s2 consist of lowercase English letters.The goal of #712 Minimum ASCII Delete Sum for Two Strings is to determine the minimum total ASCII value of characters that must be deleted from two strings so they become equal. Since deletions can occur in either string, this naturally leads to a Dynamic Programming formulation.
A common strategy is to think in terms of preserving characters rather than deleting them. If we identify the maximum ASCII sum of a common subsequence between the two strings, the remaining characters must be deleted. This is closely related to the Longest Common Subsequence (LCS) problem but instead of counting characters, we accumulate ASCII values.
Create a dp[i][j] table representing the best ASCII sum achievable using the first i characters of one string and the first j characters of the other. By comparing characters and choosing optimal subproblems, we compute the maximum preserved ASCII sum, which then helps derive the minimum delete sum.
This approach runs in O(m × n) time with a similar space requirement, where m and n are the lengths of the two strings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (ASCII-weighted LCS) | O(m × n) | O(m × n) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Let dp(i, j) be the answer for inputs s1[i:] and s2[j:].
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.
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.
1def minimumDeleteSum(s1: str, s2: str) -> int:
2 m, n = len(s1), len(s2)
3 dp = [[0] * (n + 1) for _ in range(m + 1)]
4
5 # Fill the last column
6 for i in range(m-1, -1, -1):
7 dp[i][n] = dp[i+1][n] + ord(s1[i])
8
9 # Fill the last row
10 for j in range(n-1, -1, -1):
11 dp[m][j] = dp[m][j+1] + ord(s2[j])
12
13 # Fill the rest of dp table
14 for i in range(m-1, -1, -1):
15 for j in range(n-1, -1, -1):
16 if s1[i] == s2[j]:
17 dp[i][j] = dp[i+1][j+1]
18 else:
19 dp[i][j] = min(dp[i+1][j] + ord(s1[i]), dp[i][j+1] + ord(s2[j]))
20
21 return dp[0][0]
22This 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.
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.
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.
1var minimumDeleteSum = function
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, dynamic programming problems like this are common in FAANG-style interviews. They test understanding of string DP patterns, optimal substructure, and how to adapt classic problems like LCS to new constraints.
A 2D dynamic programming table is typically used. The table stores the best ASCII sum for prefixes of the two strings, enabling efficient reuse of previously computed subproblems.
The optimal approach uses dynamic programming. By computing the maximum ASCII sum of a common subsequence between the two strings, we can determine which characters to keep and minimize the ASCII value of deleted characters.
Yes, the problem is closely related to the Longest Common Subsequence problem. Instead of maximizing the number of matched characters, the goal is to maximize the total ASCII value of the matched subsequence.
JavaScript's solution uses a similar strategy of recursion with memoization as C#. It recursively traverses both strings to find and store the minimum deletion cost, using a JavaScript object for memoization.