Minimum ASCII Delete Sum for Two Strings

Medium
580.

Minimum ASCII Delete Sum for Two Strings

Minimum ASCII Delete Sum for Two Strings is a medium coding problem on strings and dynamic programming, asked in Amazon and Google interviews.

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 <= 1000
  • Both strings consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • Both strings consist of lowercase English letters.

Hints for Minimum ASCII Delete Sum for Two Strings

  1. Hint 1

    This is edit distance with weights: only deletions are allowed, and each costs the character's ASCII value.

  2. Hint 2

    dp[i][j] is the cheapest way to equalise the first i characters of s1 with the first j of s2.

  3. 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

  1. Let dp[i][j] be the minimum delete sum for the prefixes s1[0..i) and s2[0..j).
  2. Seed the borders: emptying a prefix costs the sum of its ASCII values.
  3. If s1[i-1] == s2[j-1], keep both: dp[i][j] = dp[i-1][j-1].
  4. Otherwise take the cheaper of deleting s1[i-1] or s2[j-1].
  5. 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