> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-strings/712.-minimum-ascii-delete-sum-for-two-strings.md).

# 712. Minimum ASCII Delete Sum for Two Strings

## Problem Statement

<br>

Given two strings `s1` and `s2`, return *the lowest **ASCII** sum of deleted characters to make two strings equal*.

&#x20;

**Example 1:**

<pre><code><strong>Input: s1 = "sea", s2 = "eat"
</strong><strong>Output: 231
</strong><strong>Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: s1 = "delete", s2 = "leet"
</strong><strong>Output: 403
</strong><strong>Explanation: Deleting "dee" from "delete" to turn the string into "let",
</strong>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.
</code></pre>

&#x20;

**Constraints:**

* `1 <= s1.length, s2.length <= 1000`
* `s1` and `s2` consist of lowercase English letters.\ <br>

## Intuition

```
Just check the min, Like we check in LCS
If match proceed, 
Else, Check min at decr i, j

```

### Links

<https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/>

### Video Links

### Approach 1:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int find(string &s, string &t, int i, int j, vector<vector<int>> &dp){
        if(i<0 and j<0)
            return 0;

        if(i<0){
            int ret = 0;
            while(j>=0){
                ret += (int)t[j];
                j--;
            }
            return ret;
        }

        if(j<0){
            int ret = 0;
            while(i>=0){
                ret += (int)s[i];
                i--;
            }
            return ret;
        }

        if(dp[i][j] != -1)
            return dp[i][j];

        if(s[i] == t[j])
            return dp[i][j]= find(s, t, i-1, j-1, dp);

        return dp[i][j]= min((int)s[i]+find(s,t,i-1,j,dp) ,(int)t[j]+find(s,t,i,j-1, dp));
    }

    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size();
        int n = s2.size();
        vector<vector<int>> dp(m, vector<int>(n,-1));

        return find(s1, s2, m-1, n-1, dp);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###