Minimum ASCII Delete Sum for Two Strings

medium dp string

Problem

Return the lowest-ASCII cost of deletions to make two strings equal.

Inputs1='sea' s2='eat'

Output231

Delete 's' (115) and 't' (116).

input

def minimum_delete_sum(s1, s2):
    m, n = len(s1), len(s2); dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m): dp[i+1][0] = dp[i][0] + ord(s1[i])
    for j in range(n): dp[0][j+1] = dp[0][j] + ord(s2[j])
    for i in range(m):
        for j in range(n):
            if s1[i] == s2[j]: dp[i+1][j+1] = dp[i][j]
            else: dp[i+1][j+1] = min(dp[i][j+1] + ord(s1[i]), dp[i+1][j] + ord(s2[j]))
    return dp[m][n]

function minimumDeleteSum(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
  for (let i = 0; i < m; i++) dp[i+1][0] = dp[i][0] + s1.charCodeAt(i);
  for (let j = 0; j < n; j++) dp[0][j+1] = dp[0][j] + s2.charCodeAt(j);
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (s1[i] === s2[j]) dp[i+1][j+1] = dp[i][j];
      else dp[i+1][j+1] = Math.min(dp[i][j+1] + s1.charCodeAt(i), dp[i+1][j] + s2.charCodeAt(j));
    }
  return dp[m][n];
}

int minimumDeleteSum(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < m; i++) dp[i+1][0] = dp[i][0] + s1.charAt(i);
    for (int j = 0; j < n; j++) dp[0][j+1] = dp[0][j] + s2.charAt(j);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
        if (s1.charAt(i) == s2.charAt(j)) dp[i+1][j+1] = dp[i][j];
        else dp[i+1][j+1] = Math.min(dp[i][j+1] + s1.charAt(i), dp[i+1][j] + s2.charAt(j));
    }
    return dp[m][n];
}

int minimumDeleteSum(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector> dp(m + 1, vector(n + 1, 0));
    for (int i = 0; i < m; i++) dp[i+1][0] = dp[i][0] + s1[i];
    for (int j = 0; j < n; j++) dp[0][j+1] = dp[0][j] + s2[j];
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
        if (s1[i] == s2[j]) dp[i+1][j+1] = dp[i][j];
        else dp[i+1][j+1] = min(dp[i][j+1] + s1[i], dp[i+1][j] + s2[j]);
    }
    return dp[m][n];
}

Explanation

We may delete characters from either string to make them equal, and we want the smallest total ASCII value of everything deleted. This is solved with a 2D table that compares prefixes of the two strings.

dp[i][j] is the cheapest delete cost to make the first i letters of s1 match the first j letters of s2. The first row and column are seeded by deleting an entire prefix: each entry adds the ASCII code of one more character.

For the body: if s1[i] == s2[j] the letters line up for free, so dp[i+1][j+1] = dp[i][j]. Otherwise we must drop one of them — pick the cheaper: delete s1[i] (add ord(s1[i])) or delete s2[j] (add ord(s2[j])).

Example: s1='sea', s2='eat'. The common letters are 'ea'; we delete 's' (115) from the first and 't' (116) from the second, giving 231, the value at dp[m][n].

The table has (m+1)·(n+1) cells and each is filled in constant time, so the cost is O(m·n).

Time: O(m·n) Space: O(m·n)