# Minimum ASCII Delete Sum for Two Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings)
Canonical: https://scaleengineer.com/dsa/problems/minimum-ascii-delete-sum-for-two-strings
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
---
## Problem
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 <= 1000`
* `s1` and `s2` consist of lowercase English letters.

# Approaches
## Brute-Force Recursion
This approach uses a simple recursive method to solve the problem. The core idea is to explore all possible ways of deleting characters from both strings to make them equal and find the one with the minimum ASCII sum of deleted characters. At each pair of characters `(s1[i], s2[j])`, we make a decision: if they are equal, we keep them and move on; if they are not, we must delete one of them and recursively calculate the minimum cost for the rest of the strings.
**Time:** O(2^(m+n)), where m and n are the lengths of s1 and s2. In the worst case (no matching characters), each call branches into two, leading to an exponential number of calls. · **Space:** O(m + n), where m and n are the lengths of s1 and s2. This space is used by the recursion stack.
**Pros:** Simple to conceptualize and follows the problem definition directly.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
### Explanation
The function `findMinSum(i, j)` calculates the minimum deletion cost for substrings `s1.substring(i)` and `s2.substring(j)`. If the characters `s1.charAt(i)` and `s2.charAt(j)` are the same, we don't need to delete them, so we recursively call `findMinSum(i + 1, j + 1)`. If they differ, we have two choices: either delete `s1.charAt(i)` and solve for `s1.substring(i+1)` and `s2.substring(j)`, or delete `s2.charAt(j)` and solve for `s1.substring(i)` and `s2.substring(j+1)`. We choose the option that results in a smaller total deletion sum. The base cases handle situations where one or both strings are exhausted.

```java
public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        return findMinSum(s1, s2, 0, 0);
    }

    private int findMinSum(String s1, String s2, int i, int j) {
        // Base case: If both strings are empty, no more deletions are needed.
        if (i == s1.length() && j == s2.length()) {
            return 0;
        }

        // Base case: If s1 is empty, delete remaining characters of s2.
        if (i == s1.length()) {
            int deleteCost = 0;
            for (int k = j; k < s2.length(); k++) {
                deleteCost += s2.charAt(k);
            }
            return deleteCost;
        }

        // Base case: If s2 is empty, delete remaining characters of s1.
        if (j == s2.length()) {
            int deleteCost = 0;
            for (int k = i; k < s1.length(); k++) {
                deleteCost += s1.charAt(k);
            }
            return deleteCost;
        }

        // If characters are the same, no deletion is needed for these characters.
        if (s1.charAt(i) == s2.charAt(j)) {
            return findMinSum(s1, s2, i + 1, j + 1);
        } else {
            // If characters are different, we have two choices:
            // 1. Delete character from s1.
            int deleteS1 = s1.charAt(i) + findMinSum(s1, s2, i + 1, j);
            // 2. Delete character from s2.
            int deleteS2 = s2.charAt(j) + findMinSum(s1, s2, i, j + 1);
            return Math.min(deleteS1, deleteS2);
        }
    }
}
```
### Algorithm
1. Define a recursive function, let's call it `findMinSum(s1, s2, i, j)`, which computes the minimum ASCII delete sum for the suffixes `s1[i:]` and `s2[j:]`.
2. **Base Cases:**
   - If both `i` and `j` have reached the end of their respective strings, it means we have successfully matched them. The cost is 0.
   - If only `i` has reached the end of `s1`, we must delete all remaining characters in `s2` from index `j` onwards. The cost is the sum of ASCII values of `s2[j:]`.
   - If only `j` has reached the end of `s2`, we must delete all remaining characters in `s1` from index `i` onwards. The cost is the sum of ASCII values of `s1[i:]`.
3. **Recursive Step:**
   - If `s1.charAt(i) == s2.charAt(j)`, the characters match. We don't need to delete them. We move to the next characters in both strings. The cost is `findMinSum(s1, s2, i + 1, j + 1)`.
   - If `s1.charAt(i) != s2.charAt(j)`, we have two choices:
     a. Delete `s1.charAt(i)` and find the minimum sum for `s1[i+1:]` and `s2[j:]`. The cost is `s1.charAt(i) + findMinSum(s1, s2, i + 1, j)`.
     b. Delete `s2.charAt(j)` and find the minimum sum for `s1[i:]` and `s2[j+1:]`. The cost is `s2.charAt(j) + findMinSum(s1, s2, i, j + 1)`.
     We take the minimum of these two options.
4. The initial call to the function will be `findMinSum(s1, s2, 0, 0)`.

## Top-Down Dynamic Programming with Memoization
The brute-force recursive solution suffers from re-calculating the same subproblems multiple times. We can optimize this by using memoization, a technique also known as top-down dynamic programming. We store the result of each subproblem `(i, j)` in a cache or a 2D array. When the function is called again with the same `i` and `j`, we can directly return the stored result instead of re-computing it, effectively pruning the recursion tree.
**Time:** O(m * n), where m and n are the lengths of s1 and s2. Each subproblem `(i, j)` is computed only once. · **Space:** O(m * n) for the memoization table, plus O(m + n) for the recursion stack. The total space is dominated by the table, so it's O(m * n).
**Pros:** Drastically improves time complexity from exponential to polynomial.; Guaranteed to find the optimal solution within the time limits for the given constraints.; The logic closely follows the recursive thought process, making it relatively easy to transition from the brute-force solution.
**Cons:** Uses O(m*n) space for the memoization table, which can be large.; May cause a StackOverflowError for very large inputs due to deep recursion, although the given constraints (lengths up to 1000) are usually manageable.
### Explanation
We augment the recursive function with a 2D integer array `memo` of size `s1.length() x s2.length()`. Each cell `memo[i][j]` stores the minimum delete sum for `s1[i:]` and `s2[j:]`. Initially, all cells of `memo` are filled with a sentinel value like -1. When `findMinSum(i, j)` is called, it first checks `memo[i][j]`. If it's not -1, the value is returned. Otherwise, the result is computed recursively, stored in `memo[i][j]`, and then returned. This ensures that each state `(i, j)` is computed only once.

```java
public class Solution {
    private Integer[][] memo;

    public int minimumDeleteSum(String s1, String s2) {
        memo = new Integer[s1.length()][s2.length()];
        return findMinSum(s1, s2, 0, 0);
    }

    private int findMinSum(String s1, String s2, int i, int j) {
        if (i == s1.length() && j == s2.length()) {
            return 0;
        }
        if (i == s1.length()) {
            int deleteCost = 0;
            for (int k = j; k < s2.length(); k++) {
                deleteCost += s2.charAt(k);
            }
            return deleteCost;
        }
        if (j == s2.length()) {
            int deleteCost = 0;
            for (int k = i; k < s1.length(); k++) {
                deleteCost += s1.charAt(k);
            }
            return deleteCost;
        }

        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int result;
        if (s1.charAt(i) == s2.charAt(j)) {
            result = findMinSum(s1, s2, i + 1, j + 1);
        } else {
            int deleteS1 = s1.charAt(i) + findMinSum(s1, s2, i + 1, j);
            int deleteS2 = s2.charAt(j) + findMinSum(s1, s2, i, j + 1);
            result = Math.min(deleteS1, deleteS2);
        }
        
        memo[i][j] = result;
        return result;
    }
}
```
### Algorithm
1. The recursive structure is the same as the brute-force approach.
2. We introduce a 2D array, `memo[m][n]`, to store the results of subproblems. `memo[i][j]` will store the result of `findMinSum(i, j)`.
3. Initialize the `memo` table with a special value (e.g., -1) to indicate that a subproblem has not been solved yet.
4. In the recursive function, before any computation, check if `memo[i][j]` already has a computed value. If it does, return the stored value immediately.
5. If the value is not in the memo table, compute it using the same recursive logic as the brute-force approach.
6. Before returning the computed result, store it in `memo[i][j]` for future use.
7. The initial call remains `findMinSum(s1, s2, 0, 0)`.

## Bottom-Up Dynamic Programming (Tabulation)
This approach, also known as tabulation or bottom-up dynamic programming, solves the problem iteratively. It avoids recursion and builds the solution from the smallest subproblems up to the final problem. We use a 2D array, `dp`, where `dp[i][j]` represents the minimum ASCII delete sum required to make the prefixes `s1.substring(0, i)` and `s2.substring(0, j)` equal. By filling this table systematically, we can find the solution for the full strings.
**Time:** O(m * n) due to the nested loops iterating through all cells of the DP table. · **Space:** O(m * n) for the 2D DP table.
**Pros:** Avoids recursion overhead and the risk of stack overflow.; Often slightly faster in practice than the memoized recursive version due to better cache locality and no function call overhead.; The logic is systematic and easy to follow.
**Cons:** Requires O(m*n) space, which might be a concern for very large constraints, although it's acceptable for this problem.
### Explanation
We build a `(m+1) x (n+1)` table. The first row and column are initialized to handle the base cases where one of the strings is empty. For any cell `dp[i][j]`, we look at the characters `s1.charAt(i-1)` and `s2.charAt(j-1)`. If they are equal, the cost `dp[i][j]` is the same as `dp[i-1][j-1]`. If they are different, we must incur a deletion cost. The minimum cost is either by deleting `s1.charAt(i-1)` (cost `dp[i-1][j] + s1.charAt(i-1)`) or by deleting `s2.charAt(j-1)` (cost `dp[i][j-1] + s2.charAt(j-1)`). We fill the table row by row, and the value in the bottom-right cell, `dp[m][n]`, gives the final answer.

```java
public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        // Initialize first column
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i - 1][0] + s1.charAt(i - 1);
        }

        // Initialize first row
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j - 1] + s2.charAt(j - 1);
        }

        // Fill the rest of the table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int deleteS1 = dp[i - 1][j] + s1.charAt(i - 1);
                    int deleteS2 = dp[i][j - 1] + s2.charAt(j - 1);
                    dp[i][j] = Math.min(deleteS1, deleteS2);
                }
            }
        }

        return dp[m][n];
    }
}
```
### Algorithm
1. Create a 2D DP table, `dp`, of size `(m+1) x (n+1)`, where `dp[i][j]` will store the minimum ASCII delete sum to make `s1[0...i-1]` and `s2[0...j-1]` equal.
2. **Initialization (Base Cases):**
   - `dp[0][0] = 0` (making two empty strings equal costs 0).
   - Fill the first row: `dp[0][j]` is the cost of making an empty string and `s2[0...j-1]` equal, which requires deleting all characters of the `s2` prefix. So, `dp[0][j] = dp[0][j-1] + s2.charAt(j-1)`.
   - Fill the first column: `dp[i][0]` is the cost of making `s1[0...i-1]` and an empty string equal. So, `dp[i][0] = dp[i-1][0] + s1.charAt(i-1)`.
3. **Fill the rest of the table:** Iterate with `i` from 1 to `m` and `j` from 1 to `n`.
   - If `s1.charAt(i-1) == s2.charAt(j-1)`, the last characters match. No deletion is needed for them. The cost is inherited from the subproblem without these characters: `dp[i][j] = dp[i-1][j-1]`.
   - If `s1.charAt(i-1) != s2.charAt(j-1)`, we must delete one of them. We take the minimum of two choices:
     a. Delete `s1.charAt(i-1)`: `dp[i-1][j] + s1.charAt(i-1)`.
     b. Delete `s2.charAt(j-1)`: `dp[i][j-1] + s2.charAt(j-1)`.
     So, `dp[i][j] = Math.min(dp[i-1][j] + s1.charAt(i-1), dp[i][j-1] + s2.charAt(j-1))`.
4. **Result:** The final answer is in `dp[m][n]`, which represents the minimum delete sum for the entire `s1` and `s2`.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach in terms of space. By analyzing the state transitions of the bottom-up DP, we notice that calculating `dp[i][j]` only requires values from the current row (`dp[i][j-1]`) and the previous row (`dp[i-1][j]` and `dp[i-1][j-1]`). This dependency allows us to discard rows that are no longer needed, reducing the space complexity from `O(m*n)` to `O(n)` (or `O(min(m, n))`). We can achieve this by using a single 1D array to represent the current row being computed, while cleverly storing the necessary values from the previous row.
**Time:** O(m * n), as we still need to compute the value for each of the m*n states. · **Space:** O(min(m, n)). We use a 1D array whose size is proportional to the length of the shorter string.
**Pros:** Most space-efficient solution.; Maintains the optimal O(m*n) time complexity.
**Cons:** The logic is slightly more complex to implement correctly compared to the 2D DP approach, as it requires careful management of state within a single array.
### Explanation
We use a 1D array `dp` of size `n+1`. This array will store the values of one row of our conceptual 2D DP table. We iterate through `s1` character by character, and for each character, we update the `dp` array to compute the next row. A key detail is that when computing the new `dp[j]`, we need the old `dp[j]` (from the previous row) and the old `dp[j-1]` (also from the previous row). Since `dp[j-1]` is updated before `dp[j]`, we need an extra variable, `prev_row_j_minus_1`, to hold the value of `dp[i-1][j-1]` before it's overwritten.

```java
public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // Ensure s2 is the shorter string to optimize space
        if (m < n) {
            return minimumDeleteSum(s2, s1);
        }

        int[] dp = new int[n + 1];

        // Initialize first row
        for (int j = 1; j <= n; j++) {
            dp[j] = dp[j - 1] + s2.charAt(j - 1);
        }

        // Fill the table row by row
        for (int i = 1; i <= m; i++) {
            int prev_row_j_minus_1 = dp[0]; // This is dp[i-1][j-1] for j=1
            dp[0] += s1.charAt(i - 1); // Update first column value for current row

            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // This is dp[i-1][j]
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[j] = prev_row_j_minus_1;
                } else {
                    // dp[j] is old dp[i-1][j], dp[j-1] is new dp[i][j-1]
                    dp[j] = Math.min(dp[j] + s1.charAt(i - 1), dp[j - 1] + s2.charAt(j - 1));
                }
                prev_row_j_minus_1 = temp;
            }
        }

        return dp[n];
    }
}
```
### Algorithm
1. Observe that to compute the current row `i` of the DP table, we only need values from the previous row `i-1`.
2. We can optimize space by using only a 1D array, `dp`, of size `n+1`, where `n` is the length of the shorter string (to minimize space usage).
3. Let's assume `s2` is the shorter string. Initialize the `dp` array to represent the first row of the 2D table: `dp[j]` will be the sum of ASCII values of `s2[0...j-1]`.
4. Iterate through `s1` from `i = 1` to `m`. In each iteration, we will compute the values for the current row.
5. Inside the loop for `i`, we need to maintain the value of `dp[i-1][j-1]` (the 'top-left' cell). Let's use a variable `prev_row_j_minus_1` for this.
6. For each `i`, first update `dp[0]` (the first column value). Then, loop through `j` from 1 to `n`:
   - Store the current `dp[j]` (which is `dp[i-1][j]`) in a temporary variable `temp` before it gets overwritten.
   - Calculate the new `dp[j]` (which is `dp[i][j]`) using `prev_row_j_minus_1` (for the `dp[i-1][j-1]` term) and the just-updated `dp[j-1]` (for the `dp[i][j-1]` term).
   - Update `prev_row_j_minus_1` to `temp` for the next `j`'s iteration.
7. After the loops complete, `dp[n]` will hold the final answer.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {string} s1 * @param {string} s2 * @return {number} */ var minimumDeleteSum = function ( s1 , s2 ) { const m = s1 . length ; const n = s2 . length ; const f = Array . from ({ length : m + 1 }, () => Array ( n + 1 ). fill ( 0 )); for ( let i = 1 ; i <= m ; ++ i ) { f [ i ][ 0 ] = f [ i - 1 ][ 0 ] + s1 [ i - 1 ]. charCodeAt ( 0 ); } for ( let j = 1 ; j <= n ; ++ j ) { f [ 0 ][ j ] = f [ 0 ][ j - 1 ] + s2 [ j - 1 ]. charCodeAt ( 0 ); } for ( let i = 1 ; i <= m ; ++ i ) { for ( let j = 1 ; j <= n ; ++ j ) { if ( s1 [ i - 1 ] === s2 [ j - 1 ]) { f [ i ][ j ] = f [ i - 1 ][ j - 1 ]; } else { f [ i ][ j ] = Math . min ( f [ i - 1 ][ j ] + s1 [ i - 1 ]. charCodeAt ( 0 ), f [ i ][ j - 1 ] + s2 [ j - 1 ]. charCodeAt ( 0 ), ); } } } return f [ m ][ n ]; };
```

### CPP

```cpp
class Solution {
public:
  int minimumDeleteSum(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    int f[m + 1][n + 1];
    memset(f, 0, sizeof f);
    for (int i = 1; i <= m; ++i) {
      f[i][0] = f[i - 1][0] + s1[i - 1];
    }
    for (int j = 1; j <= n; ++j) {
      f[0][j] = f[0][j - 1] + s2[j - 1];
    }
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (s1[i - 1] == s2[j - 1]) {
          f[i][j] = f[i - 1][j - 1];
        } else {
          f[i][j] = min(f[i - 1][j] + s1[i - 1], f[i][j - 1] + s2[j - 1]);
        }
      }
    }
    return f[m][n];
  }
};

```

### Python

```python
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int: m, n = len(s1), len(s2) f = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): f[i][0] = f[i - 1][0] + ord(s1[i - 1]) for j in range(1, n + 1): f[0][j] = f[0][j - 1] + ord(s2[j - 1]) for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: f[i][j] = f[i - 1][j - 1] else: f[i][j] = min(f[i - 1][j] + ord(s1[i - 1]), f[i][j - 1] + ord(s2[j - 1])) return f[m][n]

```