Back to Coding Stuff

Leetcode 712. Minimum ASCII Delete Sum for Two Strings

10 January 2026
•
5 min read
Dynamic ProgrammingStringBacktrackingMemoizationLeetcode

Problem Description

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] = 302 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.

Initial Approach: Backtracking

Thought Process

The initial approach uses backtracking to explore all possible ways to make the strings equal:

1. If characters match: Move both pointers forward without adding to the sum

2. If characters don't match: Try two options:

- Delete from s1: Add ASCII value of s1[i] and move i forward

- Delete from s2: Add ASCII value of s2[j] and move j forward

3. Base cases: When one string is exhausted, delete all remaining characters from the other string

Initial Code (Backtracking - TLE)

java
class Solution {
    int ans = Integer.MAX_VALUE;
    public int minimumDeleteSum(String s1, String s2) {
        check(s1,s2,0,0,0);
        return ans;
    }

    void check(String s1, String s2, int i, int j, int cur){
        if(i == s1.length() && j == s2.length()){
            ans = Math.min(ans,cur);
            return;
        }
        if(i >= s1.length()){
            check(s1,s2,i,j+1,cur+(int)(s2.charAt(j)));
        }
        else if(j >= s2.length()){
            check(s1,s2,i+1,j,cur+(int)(s1.charAt(i)));
        }
        else if(s1.charAt(i) == s2.charAt(j)) {
            check(s1,s2,i+1,j+1,cur);
        }else{
            check(s1,s2,i+1,j,cur+(int)(s1.charAt(i)));
            check(s1,s2,i,j+1,cur+(int)(s2.charAt(j)));
        }
    }
}

Why This Approach Gets TLE

The backtracking approach explores all possible deletion combinations without memoization, leading to:

  • Exponential time complexity: O(2^(m+n)) where m and n are string lengths
  • Overlapping subproblems: The same `(i, j)` state is computed multiple times
  • No caching: Each recursive path recalculates the same subproblems

    • For example, when s1 = "abc" and s2 = "def", the function will explore:

  • Delete from s1, then delete from s2
  • Delete from s2, then delete from s1

    • Both paths eventually reach the same state (i+1, j+1), but the backtracking approach recalculates it.

    Memoized Solution

    Approach

    Add memoization to cache results of subproblems. The key insight is that for a given state (i, j), the minimum delete sum is always the same, regardless of how we reached that state.

    Memoized Code

    java
    class Solution {
    Map<String,Integer> map = new HashMap<>();
    public int minimumDeleteSum(String s1, String s2) {
        return check(s1,s2,0,0);
    }

    int check(String s1, String s2, int i, int j){
        if(i == s1.length() && j == s2.length()){
            return 0;
        }
        if(i >= s1.length()){
            return s2.charAt(j) + check(s1,s2,i,j+1);
        }
        else if(j >= s2.length()){
            return s1.charAt(i) + check(s1,s2,i+1,j);
        }
        String cur = i + "," + j;
        if(map.containsKey(cur)){
            return map.get(cur);
        }
        int ans;
        if(s1.charAt(i) == s2.charAt(j)) {
            ans =  check(s1,s2,i+1,j+1);
        }else{
            int ans1 = (int)(s1.charAt(i)) + check(s1,s2,i+1,j);
            int ans2 = (int)(s2.charAt(j)) + check(s1,s2,i,j+1);
            ans = Math.min(ans1,ans2);
        }
        map.put(cur, ans);
        return ans;
    }
}

    Key Changes from Backtracking

    1. Return value instead of global variable: The function now returns the minimum sum for state (i, j) instead of updating a global ans

    2. Memoization: Results are cached in a HashMap using "i,j" as the key

    3. Base case returns 0: When both strings are exhausted, no more deletions are needed

    4. Base cases for exhaustion: When one string is exhausted, return the sum of remaining characters in the other string

    How Memoization Works

    Example: s1 = "sea", s2 = "eat"

State (0,0): 's' != 'e'
  - Option 1: Delete 's' → go to (1,0) → cost = 115 + result(1,0)
  - Option 2: Delete 'e' → go to (0,1) → cost = 101 + result(0,1)
  - Cache result(0,0) = min(115 + result(1,0), 101 + result(0,1))

State (1,0): 'e' == 'e' → go to (2,1) without cost
State (2,1): 'a' == 'a' → go to (3,2) without cost
State (3,2): s1 exhausted, delete remaining in s2 → 't' = 116

Result: 115 + 116 = 231

    Time & Space Complexity

  • Time Complexity: O(m × n) - Each state `(i, j)` is computed once
  • Space Complexity: O(m × n) - HashMap stores results for all states, plus O(m + n) for recursion stack

    • Optimal Solution: 2D Dynamic Programming

    Approach

    Convert the memoized recursive solution to an iterative 2D DP approach:

  • `dp[i][j]` = minimum ASCII delete sum for `s1[i..]` and `s2[j..]`
  • Build from bottom-up (end of strings to beginning)
  • This eliminates recursion stack overhead

    • Optimal Code

    java
    class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        
        // dp[i][j] = minimum delete sum for s1[i..m-1] and s2[j..n-1]
        int[][] dp = new int[m + 1][n + 1];
        
        // Base case: if both strings are exhausted, cost is 0
        dp[m][n] = 0;
        
        // Base case: if s1 is exhausted, delete all remaining in s2
        for (int j = n - 1; j >= 0; j--) {
            dp[m][j] = dp[m][j + 1] + s2.charAt(j);
        }
        
        // Base case: if s2 is exhausted, delete all remaining in s1
        for (int i = m - 1; i >= 0; i--) {
            dp[i][n] = dp[i + 1][n] + s1.charAt(i);
        }
        
        // Fill the DP table
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    // Characters match, no deletion needed
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    // Delete from s1 or s2, take minimum
                    dp[i][j] = Math.min(
                        s1.charAt(i) + dp[i + 1][j],
                        s2.charAt(j) + dp[i][j + 1]
                    );
                }
            }
        }
        
        return dp[0][0];
    }
}

    Explanation

    Base Cases

    1. Both exhausted: dp[m][n] = 0 - No deletions needed

    2. s1 exhausted: dp[m][j] = dp[m][j+1] + s2.charAt(j) - Delete all remaining characters in s2

    3. s2 exhausted: dp[i][n] = dp[i+1][n] + s1.charAt(i) - Delete all remaining characters in s1

    Recurrence Relation

    For dp[i][j]:

  • If `s1[i] == s2[j]`: Characters match, no deletion needed → `dp[i][j] = dp[i+1][j+1]`
  • If `s1[i] != s2[j]`: Delete from either string, take minimum:

    • - Delete from s1: s1.charAt(i) + dp[i+1][j]

    - Delete from s2: s2.charAt(j) + dp[i][j+1]

    - dp[i][j] = min(delete from s1, delete from s2)

    Example Walkthrough

    s1 = "sea", s2 = "eat"

DP Table (filled bottom-up):
      e    a    t    [end]
s  [231] [316] [417] [403]
e  [116] [231] [332] [403]
a   [97] [116] [231] [332]
[end] [101] [198] [314] [0]

Calculation for dp[0][0]:
- s[0]='s', e[0]='e' → different
- Option 1: Delete 's' → 115 + dp[1][0] = 115 + 116 = 231
- Option 2: Delete 'e' → 101 + dp[0][1] = 101 + 316 = 417
- dp[0][0] = min(231, 417) = 231

Final answer: 231

    Space Optimization

    We can optimize space from O(m × n) to O(n) since we only need the previous row:

    java
    class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        
        int[] prev = new int[n + 1];
        int[] curr = new int[n + 1];
        
        // Base case: if s2 is exhausted
        for (int j = n - 1; j >= 0; j--) {
            prev[j] = prev[j + 1] + s2.charAt(j);
        }
        
        for (int i = m - 1; i >= 0; i--) {
            // Base case: if s1 is exhausted (for current row)
            curr[n] = prev[n] + s1.charAt(i);
            
            for (int j = n - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    curr[j] = prev[j + 1];
                } else {
                    curr[j] = Math.min(
                        s1.charAt(i) + prev[j],
                        s2.charAt(j) + curr[j + 1]
                    );
                }
            }
            
            // Swap arrays
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        
        return prev[0];
    }
}

    Comparison

    ApproachTimeSpaceNotes
    BacktrackingO(2^(m+n))O(m+n)TLE on large inputs
    Memoized RecursionO(m×n)O(m×n)Works, but recursion overhead
    2D DPO(m×n)O(m×n)Iterative, no recursion
    Space-Optimized DPO(m×n)O(n)Best space complexity

    Summary

    1. Initial backtracking approach explores all deletion combinations but gets TLE due to exponential time complexity

    2. Memoization fixes the TLE by caching subproblem results, reducing time to O(m×n)

    3. 2D DP solution converts recursion to iteration, eliminating stack overhead

    4. Space-optimized DP further reduces space to O(n) by using only two rows

    The key insight is recognizing this as a variant of the Longest Common Subsequence (LCS) problem, where instead of finding the LCS, we're finding the minimum cost to delete characters to make strings equal.