Minimum ASCII Delete Sum for Two Strings — Solution
Minimum ASCII Delete Sum for Two Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum ASCII Delete Sum for Two Strings is a medium coding problem on strings and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two strings s1 and s2, delete characters from either until they are equal.
Return the lowest possible sum of the ASCII values of the deleted characters.
Example 1
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Delete s from s1 (115) and t from s2 (116) — 231 in total.
Example 2
Input: s1 = "delete", s2 = "leet"
Output: 403
Example 3
Input: s1 = "a", s2 = "a"
Output: 0
Constraints
1 <= s1.length, s2.length <= 1000Both strings consist of lowercase English letters.
Hints for Minimum ASCII Delete Sum for Two Strings
Hint 1
This is edit distance with weights: only deletions are allowed, and each costs the character's ASCII value.
Hint 2
dp[i][j]is the cheapest way to equalise the firsticharacters ofs1with the firstjofs2.Hint 3
Matching characters cost nothing; otherwise delete from one side or the other.
How to solve Minimum ASCII Delete Sum for Two Strings
A weighted LCS. Rather than maximising what you keep, minimise the ASCII weight of what you throw away — which the table does directly.
Approach
- Let
dp[i][j]be the minimum delete sum for the prefixess1[0..i)ands2[0..j). - Seed the borders: emptying a prefix costs the sum of its ASCII values.
- If
s1[i-1] == s2[j-1], keep both:dp[i][j] = dp[i-1][j-1]. - Otherwise take the cheaper of deleting
s1[i-1]ors2[j-1]. - Return
dp[n][m].
Why it works
Only the last characters of the two prefixes matter. If they match there is an optimal solution keeping both — swapping them in never costs more. If they differ, at least one must be deleted, and the recurrence tries both choices.
Complexity
- Time —
O(n · m) - Space —
O(n · m), reducible to O(m)
Pitfalls
- Zeroing the borders instead of accumulating ASCII sums makes deletions free at the edges.
- Maximising the kept LCS length is not the same as minimising the deleted ASCII weight — a long run of cheap characters can beat a short run of expensive ones.
- The totals reach roughly 122,000 at the limits, safely inside 32 bits.
Reference solution
Python
def minimumDeleteSum(s1: str, s2: str) -> int:
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
for j in range(1, m + 1):
dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
for i in range(1, n + 1):
for j in range(1, m + 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[n][m]Java
public static int minimumDeleteSum(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
for (int j = 1; j <= m; j++) dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j - 1));
}
}
return dp[n][m];
}C++
int minimumDeleteSum(string s1, string s2) {
int n = (int) s1.size(), m = (int) s2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + s1[i - 1];
for (int j = 1; j <= m; j++) dp[0][j] = dp[0][j - 1] + s2[j - 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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] + s1[i - 1], dp[i][j - 1] + s2[j - 1]);
}
}
return dp[n][m];
}JavaScript
var minimumDeleteSum = function(s1, s2) {
const n = s1.length, m = s2.length;
const dp = [];
for (let i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(0));
for (let i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + s1.charCodeAt(i - 1);
for (let j = 1; j <= m; j++) dp[0][j] = dp[0][j - 1] + s2.charCodeAt(j - 1);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; 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] + s1.charCodeAt(i - 1), dp[i][j - 1] + s2.charCodeAt(j - 1));
}
}
return dp[n][m];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming