# LeetCode 712: Minimum ASCII Delete Sum for Two Strings

## Problem Restatement

We are given two strings:

```python
s1
s2
```

We may delete characters from either string.

Deleting a character costs its ASCII value.

We need to make the two strings equal with the minimum total deletion cost.

Return that minimum cost.

For example, deleting `"s"` costs:

```python
ord("s") = 115
```

The strings contain lowercase English letters, and their lengths are between `1` and `1000`. The official problem asks for the lowest ASCII sum of deleted characters needed to make the two strings equal.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two strings `s1` and `s2` |
| Output | Minimum ASCII sum of deleted characters |
| Operation | Delete a character from either string |
| Goal | Make the remaining strings equal |
| Characters | Lowercase English letters |

The function shape is:

```python
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        ...
```

## Examples

Example 1:

```python
s1 = "sea"
s2 = "eat"
```

One optimal way is:

```python
"sea" -> "ea"    delete "s", cost 115
"eat" -> "ea"    delete "t", cost 116
```

Total cost:

```python
115 + 116 = 231
```

Output:

```python
231
```

Example 2:

```python
s1 = "delete"
s2 = "leet"
```

One optimal result is to make both strings equal to:

```python
"let"
```

Delete `"dee"` from `"delete"`:

```python
ord("d") + ord("e") + ord("e") = 100 + 101 + 101
```

Delete `"e"` from `"leet"`:

```python
101
```

Total:

```python
100 + 101 + 101 + 101 = 403
```

Output:

```python
403
```

## First Thought: Try All Deletions

A brute force approach is to try every possible way to delete characters from both strings.

At each position, we could:

1. Keep matching characters.
2. Delete from `s1`.
3. Delete from `s2`.

This quickly becomes exponential because the same suffix pairs are solved many times.

For strings of length up to `1000`, brute force is impossible.

## Key Insight

This is a dynamic programming problem.

The useful state is:

```python
dp[i][j]
```

where `dp[i][j]` means:

Minimum ASCII deletion cost needed to make:

```python
s1[:i]
s2[:j]
```

equal.

That means we solve the problem for prefixes of both strings.

The final answer is:

```python
dp[len(s1)][len(s2)]
```

## Recurrence

Let:

```python
a = s1[i - 1]
b = s2[j - 1]
```

If the last characters match:

```python
a == b
```

we do not need to delete either of them.

So:

```python
dp[i][j] = dp[i - 1][j - 1]
```

If they do not match, we have two choices.

Delete `a` from `s1`:

```python
dp[i - 1][j] + ord(a)
```

Delete `b` from `s2`:

```python
dp[i][j - 1] + ord(b)
```

Take the cheaper option:

```python
dp[i][j] = min(
    dp[i - 1][j] + ord(a),
    dp[i][j - 1] + ord(b),
)
```

## Base Cases

If `s2` is empty, we must delete all characters from `s1[:i]`.

```python
dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
```

If `s1` is empty, we must delete all characters from `s2[:j]`.

```python
dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
```

Also:

```python
dp[0][0] = 0
```

Two empty strings already match.

## Algorithm

1. Let `m = len(s1)` and `n = len(s2)`.
2. Create a DP table of size `(m + 1) x (n + 1)`.
3. Fill the first column by deleting from `s1`.
4. Fill the first row by deleting from `s2`.
5. For every `i` from `1` to `m`:
   - For every `j` from `1` to `n`:
     - If `s1[i - 1] == s2[j - 1]`, copy `dp[i - 1][j - 1]`.
     - Otherwise, choose the cheaper deletion.
6. Return `dp[m][n]`.

## Correctness

We prove that `dp[i][j]` stores the minimum deletion cost needed to make `s1[:i]` and `s2[:j]` equal.

For the base cases, if one prefix is empty, the only way to make the strings equal is to delete every character from the other prefix. The initialization sums exactly those ASCII costs, so the base cases are correct.

For non-empty prefixes, consider the last characters `s1[i - 1]` and `s2[j - 1]`.

If they are equal, an optimal solution can keep both characters at the end. Then we only need to make the earlier prefixes `s1[:i - 1]` and `s2[:j - 1]` equal. This costs `dp[i - 1][j - 1]`.

If they are different, they cannot both remain as the final matching character. At least one of them must be deleted. If we delete `s1[i - 1]`, the remaining cost is `dp[i - 1][j] + ord(s1[i - 1])`. If we delete `s2[j - 1]`, the remaining cost is `dp[i][j - 1] + ord(s2[j - 1])`. Taking the minimum gives the best possible cost.

Thus every DP state is computed correctly from smaller correct states. Therefore `dp[m][n]` is the minimum cost for the full strings.

## Complexity

Let:

```python
m = len(s1)
n = len(s2)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(mn)` | We fill one DP cell for each pair of prefixes |
| Space | `O(mn)` | The full DP table has `(m + 1)(n + 1)` cells |

## Implementation

```python
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = len(s2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])

        for j in range(1, n + 1):
            dp[0][j] = dp[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]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    delete_from_s1 = dp[i - 1][j] + ord(s1[i - 1])
                    delete_from_s2 = dp[i][j - 1] + ord(s2[j - 1])

                    dp[i][j] = min(delete_from_s1, delete_from_s2)

        return dp[m][n]
```

## Code Explanation

First, get the string lengths:

```python
m = len(s1)
n = len(s2)
```

Create the DP table:

```python
dp = [[0] * (n + 1) for _ in range(m + 1)]
```

Initialize the first column:

```python
for i in range(1, m + 1):
    dp[i][0] = dp[i - 1][0] + ord(s1[i - 1])
```

This means `s2` is empty, so we delete all characters from `s1`.

Initialize the first row:

```python
for j in range(1, n + 1):
    dp[0][j] = dp[0][j - 1] + ord(s2[j - 1])
```

This means `s1` is empty, so we delete all characters from `s2`.

For matching last characters:

```python
if s1[i - 1] == s2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1]
```

No deletion is needed for those two characters.

For different last characters:

```python
delete_from_s1 = dp[i - 1][j] + ord(s1[i - 1])
delete_from_s2 = dp[i][j - 1] + ord(s2[j - 1])
```

Choose the cheaper deletion:

```python
dp[i][j] = min(delete_from_s1, delete_from_s2)
```

Finally:

```python
return dp[m][n]
```

## Space-Optimized Implementation

Each DP row only depends on the previous row and the current row.

So we can reduce space from `O(mn)` to `O(n)`.

```python
class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = len(s2)

        dp = [0] * (n + 1)

        for j in range(1, n + 1):
            dp[j] = dp[j - 1] + ord(s2[j - 1])

        for i in range(1, m + 1):
            prev_diagonal = dp[0]
            dp[0] += ord(s1[i - 1])

            for j in range(1, n + 1):
                old_dp_j = dp[j]

                if s1[i - 1] == s2[j - 1]:
                    dp[j] = prev_diagonal
                else:
                    delete_from_s1 = dp[j] + ord(s1[i - 1])
                    delete_from_s2 = dp[j - 1] + ord(s2[j - 1])
                    dp[j] = min(delete_from_s1, delete_from_s2)

                prev_diagonal = old_dp_j

        return dp[n]
```

## Testing

```python
def test_minimum_delete_sum():
    s = Solution()

    assert s.minimumDeleteSum("sea", "eat") == 231
    assert s.minimumDeleteSum("delete", "leet") == 403
    assert s.minimumDeleteSum("a", "a") == 0
    assert s.minimumDeleteSum("a", "b") == ord("a") + ord("b")
    assert s.minimumDeleteSum("abc", "abc") == 0
    assert s.minimumDeleteSum("abc", "def") == sum(map(ord, "abcdef"))

    print("all tests passed")

test_minimum_delete_sum()
```

Test coverage:

| Test | Why |
|---|---|
| `"sea"`, `"eat"` | Confirms standard example |
| `"delete"`, `"leet"` | Confirms larger overlapping subsequence |
| Equal one-character strings | Confirms no deletion |
| Different one-character strings | Confirms both must be deleted |
| Equal strings | Confirms zero cost |
| No shared characters | Confirms all characters are deleted |