Minimum ASCII Delete Sum

🎯

Minimum ASCII Delete Sum

mediumDPAmazonGoogle

Imagine you want to make two strings identical by deleting characters, but each deletion costs you the ASCII value of the deleted character. How do you minimize the total cost?

💡 This problem is a classic example of string dynamic programming where we want to find the minimum cost to make two strings equal by deleting characters. Beginners often struggle because it combines concepts of LCS with weighted deletions, requiring careful state definition and transitions.

📋

Problem Statement

Given two strings s1 and s2, return the minimum ASCII sum of deleted characters to make the two strings equal. You can delete characters from either string.

1 ≤ s1.length, s2.length ≤ 1000s1 and s2 consist of lowercase and uppercase English letters

💡

Example

Input"s1 = \"sea\", s2 = \"eat\""

Output231

Delete 's' from s1 (ASCII 115) and 't' from s2 (ASCII 116), total 231.

Input"s1 = \"delete\", s2 = \"leet\""

Output403

Delete 'd', 'e', 'e' from s1 and 't' from s2 to make both "leet".

• One string empty, other non-empty → sum of ASCII of all characters in non-empty string
• Both strings identical → 0 cost
• Strings with no common characters → sum of ASCII of all characters in both strings
• Strings with repeated characters → ensure correct handling of multiple deletions

🔁

Why DP?

Why greedy fails:

A greedy approach might delete characters with the smallest ASCII values first, but this can lead to suboptimal solutions. For example, deleting a small ASCII character early might prevent matching a longer common subsequence later, increasing total cost.

DP state:

dp[i][j] represents the minimum ASCII delete sum to make s1[0..i-1] and s2[0..j-1] equal.

Recurrence:dp[i][j] = if s1[i-1] == s2[j-1] then dp[i-1][j-1] else min(dp[i-1][j] + ASCII(s1[i-1]), dp[i][j-1] + ASCII(s2[j-1]))

If the current characters match, no deletion cost is added; otherwise, delete one character from either string and add its ASCII value to the minimal cost.

⚠️

Common Mistakes

Not handling base cases correctly

Incorrect results or index errors

✅ Initialize dp arrays properly with cumulative ASCII sums for empty prefixes

Mixing up indices (off-by-one errors)

Wrong character comparisons or dp accesses

✅ Carefully use i-1 and j-1 when accessing string characters

Forgetting to cache results in memoization

Solution reverts to exponential time

✅ Store computed results in memo before returning

Incorrect iteration order in space optimized DP

Overwrites dp values prematurely, leading to wrong answers

✅ Iterate dp array backwards when updating to preserve dependencies

Assuming greedy deletion of smallest ASCII chars works

Suboptimal total cost, fails test cases

✅ Use DP to consider all deletion combinations

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated subproblems.

Intuition

Try all ways to delete characters from either string until they match, summing ASCII values of deleted characters.

Algorithm

1. If either string is empty, return sum of ASCII values of the other string.
2. If last characters match, recurse on both strings without deleting.
3. Otherwise, recurse by deleting last character from s1 or s2 and add its ASCII value.
4. Return the minimum cost from the two deletion options.

💡 The recursion is straightforward but leads to exponential calls due to overlapping subproblems.

Recurrence:dp(i,j) = if s1[i-1] == s2[j-1] then dp(i-1,j-1) else min(dp(i-1,j) + ASCII(s1[i-1]), dp(i,j-1) + ASCII(s2[j-1]))

</>

Code

def minimumDeleteSum(s1: str, s2: str) -> int:
    def helper(i, j):
        if i == 0 and j == 0:
            return 0
        if i == 0:
            return sum(ord(c) for c in s2[:j])
        if j == 0:
            return sum(ord(c) for c in s1[:i])
        if s1[i-1] == s2[j-1]:
            return helper(i-1, j-1)
        else:
            return min(helper(i-1, j) + ord(s1[i-1]), helper(i, j-1) + ord(s2[j-1]))
    return helper(len(s1), len(s2))

# Example usage:
if __name__ == '__main__':
    print(minimumDeleteSum("sea", "eat"))  # Output: 231

Line Notes

def helper(i, j):Defines recursive helper to compute cost for prefixes s1[:i], s2[:j]

if i == 0 and j == 0:Base case: both strings empty, no cost

if i == 0:If s1 empty, cost is sum of ASCII of s2 prefix

if s1[i-1] == s2[j-1]:If last chars match, no deletion needed, recurse on smaller prefixes

public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        return helper(s1, s2, s1.length(), s2.length());
    }
    private int helper(String s1, String s2, int i, int j) {
        if (i == 0 && j == 0) return 0;
        if (i == 0) {
            int sum = 0;
            for (int k = 0; k < j; k++) sum += s2.charAt(k);
            return sum;
        }
        if (j == 0) {
            int sum = 0;
            for (int k = 0; k < i; k++) sum += s1.charAt(k);
            return sum;
        }
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            return helper(s1, s2, i - 1, j - 1);
        } else {
            return Math.min(helper(s1, s2, i - 1, j) + s1.charAt(i - 1),
                            helper(s1, s2, i, j - 1) + s2.charAt(j - 1));
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minimumDeleteSum("sea", "eat")); // 231
    }
}

Line Notes

private int helper(String s1, String s2, int i, int j)Recursive helper for prefixes s1[0..i-1], s2[0..j-1]

if (i == 0 && j == 0) return 0;Base case: both empty strings

for (int k = 0; k < j; k++) sum += s2.charAt(k);Sum ASCII values if s1 empty

if (s1.charAt(i - 1) == s2.charAt(j - 1))If last chars match, recurse without deletion

#include <iostream>
#include <string>
#include <numeric>
using namespace std;

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        return helper(s1, s2, s1.size(), s2.size());
    }
private:
    int helper(const string& s1, const string& s2, int i, int j) {
        if (i == 0 && j == 0) return 0;
        if (i == 0) return accumulate(s2.begin(), s2.begin() + j, 0);
        if (j == 0) return accumulate(s1.begin(), s1.begin() + i, 0);
        if (s1[i - 1] == s2[j - 1]) {
            return helper(s1, s2, i - 1, j - 1);
        } else {
            return min(helper(s1, s2, i - 1, j) + s1[i - 1],
                       helper(s1, s2, i, j - 1) + s2[j - 1]);
        }
    }
};

int main() {
    Solution sol;
    cout << sol.minimumDeleteSum("sea", "eat") << endl; // 231
    return 0;
}

Line Notes

int helper(const string& s1, const string& s2, int i, int j)Recursive helper for prefixes

if (i == 0 && j == 0) return 0;Base case both empty

return accumulate(s2.begin(), s2.begin() + j, 0);Sum ASCII if s1 empty

if (s1[i - 1] == s2[j - 1])If chars match, recurse without deletion

function minimumDeleteSum(s1, s2) {
    function helper(i, j) {
        if (i === 0 && j === 0) return 0;
        if (i === 0) return [...s2.slice(0, j)].reduce((a, c) => a + c.charCodeAt(0), 0);
        if (j === 0) return [...s1.slice(0, i)].reduce((a, c) => a + c.charCodeAt(0), 0);
        if (s1[i - 1] === s2[j - 1]) {
            return helper(i - 1, j - 1);
        } else {
            return Math.min(helper(i - 1, j) + s1.charCodeAt(i - 1),
                            helper(i, j - 1) + s2.charCodeAt(j - 1));
        }
    }
    return helper(s1.length, s2.length);
}

console.log(minimumDeleteSum("sea", "eat")); // 231

Line Notes

function helper(i, j)Recursive helper for prefixes s1[0..i-1], s2[0..j-1]

if (i === 0 && j === 0) return 0;Base case both empty

return [...s2.slice(0, j)].reduce((a, c) => a + c.charCodeAt(0), 0);Sum ASCII if s1 empty

if (s1[i - 1] === s2[j - 1])If chars match, recurse without deletion

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each call branches into two calls unless characters match, leading to exponential calls.

💡 For strings of length 10, this could mean over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down Memoization

💡 Memoization avoids recomputing states by caching results, drastically improving efficiency while preserving the recursive intuition.

Intuition

Store results of subproblems in a cache so that repeated calls return instantly instead of recomputing.

Algorithm

1. Initialize a 2D cache to store results for each prefix pair.
2. If result for dp[i][j] is cached, return it immediately.
3. If characters match, recurse on smaller prefixes without cost.
4. Otherwise, compute minimal cost by deleting from either string and cache the result.

💡 Memoization keeps the recursive structure but avoids exponential blowup by caching.

Recurrence:dp(i,j) = if s1[i-1] == s2[j-1] then dp(i-1,j-1) else min(dp(i-1,j) + ASCII(s1[i-1]), dp(i,j-1) + ASCII(s2[j-1]))

</>

Code

def minimumDeleteSum(s1: str, s2: str) -> int:
    from functools import lru_cache
    @lru_cache(None)
    def helper(i, j):
        if i == 0 and j == 0:
            return 0
        if i == 0:
            return sum(ord(c) for c in s2[:j])
        if j == 0:
            return sum(ord(c) for c in s1[:i])
        if s1[i-1] == s2[j-1]:
            return helper(i-1, j-1)
        else:
            return min(helper(i-1, j) + ord(s1[i-1]), helper(i, j-1) + ord(s2[j-1]))
    return helper(len(s1), len(s2))

# Example usage:
if __name__ == '__main__':
    print(minimumDeleteSum("sea", "eat"))  # Output: 231

Line Notes

@lru_cache(None)Caches results of helper calls to avoid recomputation

def helper(i, j):Recursive helper with memoization

if i == 0:Base case: sum ASCII of s2 prefix if s1 empty

return min(helper(i-1, j) + ord(s1[i-1]), helper(i, j-1) + ord(s2[j-1]))Choose minimal deletion cost

import java.util.*;
public class Solution {
    private Integer[][] memo;
    public int minimumDeleteSum(String s1, String s2) {
        memo = new Integer[s1.length() + 1][s2.length() + 1];
        return helper(s1, s2, s1.length(), s2.length());
    }
    private int helper(String s1, String s2, int i, int j) {
        if (i == 0 && j == 0) return 0;
        if (memo[i][j] != null) return memo[i][j];
        if (i == 0) {
            int sum = 0;
            for (int k = 0; k < j; k++) sum += s2.charAt(k);
            memo[i][j] = sum;
            return sum;
        }
        if (j == 0) {
            int sum = 0;
            for (int k = 0; k < i; k++) sum += s1.charAt(k);
            memo[i][j] = sum;
            return sum;
        }
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            memo[i][j] = helper(s1, s2, i - 1, j - 1);
        } else {
            memo[i][j] = Math.min(helper(s1, s2, i - 1, j) + s1.charAt(i - 1),
                                  helper(s1, s2, i, j - 1) + s2.charAt(j - 1));
        }
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minimumDeleteSum("sea", "eat")); // 231
    }
}

Line Notes

private Integer[][] memo;Cache to store computed results for subproblems

if (memo[i][j] != null) return memo[i][j];Return cached result if available

memo[i][j] = ...Store computed result before returning

if (s1.charAt(i - 1) == s2.charAt(j - 1))No deletion cost if chars match

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> memo;
    int minimumDeleteSum(string s1, string s2) {
        memo.assign(s1.size() + 1, vector<int>(s2.size() + 1, -1));
        return helper(s1, s2, s1.size(), s2.size());
    }
private:
    int helper(const string& s1, const string& s2, int i, int j) {
        if (i == 0 && j == 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (i == 0) {
            int sum = 0;
            for (int k = 0; k < j; k++) sum += s2[k];
            return memo[i][j] = sum;
        }
        if (j == 0) {
            int sum = 0;
            for (int k = 0; k < i; k++) sum += s1[k];
            return memo[i][j] = sum;
        }
        if (s1[i - 1] == s2[j - 1]) {
            return memo[i][j] = helper(s1, s2, i - 1, j - 1);
        } else {
            return memo[i][j] = min(helper(s1, s2, i - 1, j) + s1[i - 1],
                                   helper(s1, s2, i, j - 1) + s2[j - 1]);
        }
    }
};

int main() {
    Solution sol;
    cout << sol.minimumDeleteSum("sea", "eat") << endl; // 231
    return 0;
}

Line Notes

vector<vector<int>> memo;2D vector to cache results

if (memo[i][j] != -1) return memo[i][j];Return cached result if computed

memo[i][j] = ...Store computed result

if (s1[i - 1] == s2[j - 1])No deletion cost if chars match

function minimumDeleteSum(s1, s2) {
    const memo = Array(s1.length + 1).fill(null).map(() => Array(s2.length + 1).fill(null));
    function helper(i, j) {
        if (i === 0 && j === 0) return 0;
        if (memo[i][j] !== null) return memo[i][j];
        if (i === 0) {
            let sum = 0;
            for (let k = 0; k < j; k++) sum += s2.charCodeAt(k);
            memo[i][j] = sum;
            return sum;
        }
        if (j === 0) {
            let sum = 0;
            for (let k = 0; k < i; k++) sum += s1.charCodeAt(k);
            memo[i][j] = sum;
            return sum;
        }
        if (s1[i - 1] === s2[j - 1]) {
            memo[i][j] = helper(i - 1, j - 1);
        } else {
            memo[i][j] = Math.min(helper(i - 1, j) + s1.charCodeAt(i - 1),
                                  helper(i, j - 1) + s2.charCodeAt(j - 1));
        }
        return memo[i][j];
    }
    return helper(s1.length, s2.length);
}

console.log(minimumDeleteSum("sea", "eat")); // 231

Line Notes

const memo = Array(s1.length + 1).fill(null).map(() => Array(s2.length + 1).fill(null));Initialize 2D memo array

if (memo[i][j] !== null) return memo[i][j];Return cached result if available

memo[i][j] = ...Cache computed result

if (s1[i - 1] === s2[j - 1])No deletion cost if chars match

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each subproblem dp[i][j] is computed once and cached, reducing exponential to polynomial time.

💡 For strings of length 1000, this means about 1 million computations, which is feasible.

Interview Verdict: Accepted

Memoization is efficient and acceptable for interview coding, showing understanding of DP optimization.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from smaller subproblems, often easier to debug and understand than recursion.

Intuition

Fill a 2D dp table where each cell represents minimal cost for prefixes, using previously computed results.

Algorithm

1. Initialize dp array with base cases: cost of deleting all characters from one string when the other is empty.
2. Iterate over all prefix lengths i and j.
3. If characters match, copy dp[i-1][j-1].
4. Otherwise, take minimum of deleting from s1 or s2 plus ASCII cost.
5. Return dp[m][n] as final answer.

💡 Tabulation explicitly shows the DP table and how each state depends on previous states.

Recurrence:dp[i][j] = if s1[i-1] == s2[j-1] then dp[i-1][j-1] else min(dp[i-1][j] + ASCII(s1[i-1]), dp[i][j-1] + ASCII(s2[j-1]))

</>

Code

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), 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:
                dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1]))
    return dp[m][n]

# Example usage:
if __name__ == '__main__':
    print(minimumDeleteSum("sea", "eat"))  # Output: 231

Line Notes

dp = [[0] * (n + 1) for _ in range(m + 1)]Initialize DP table with zeros

dp[i][0] = dp[i-1][0] + ord(s1[i-1])Cost of deleting all chars from s1 prefix when s2 empty

if s1[i-1] == s2[j-1]:If chars match, no deletion cost

dp[i][j] = min(...)Choose minimal cost between deleting from s1 or s2

public class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] + s1.charAt(i-1);
        for (int j = 1; j <= n; j++) dp[0][j] = dp[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)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j] + s1.charAt(i-1), dp[i][j-1] + s2.charAt(j-1));
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minimumDeleteSum("sea", "eat")); // 231
    }
}

Line Notes

int[][] dp = new int[m + 1][n + 1];Create DP table for all prefix pairs

dp[i][0] = dp[i-1][0] + s1.charAt(i-1);Initialize first column with deletion costs

if (s1.charAt(i-1) == s2.charAt(j-1))No cost if chars match

dp[i][j] = Math.min(...)Choose minimal deletion cost

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) dp[i][0] = dp[i-1][0] + s1[i-1];
        for (int j = 1; j <= n; j++) dp[0][j] = dp[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]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
                }
            }
        }
        return dp[m][n];
    }
};

int main() {
    Solution sol;
    cout << sol.minimumDeleteSum("sea", "eat") << endl; // 231
    return 0;
}

Line Notes

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));Initialize DP table with zeros

dp[i][0] = dp[i-1][0] + s1[i-1];Cost of deleting s1 prefix when s2 empty

if (s1[i-1] == s2[j-1])No deletion cost if chars match

dp[i][j] = min(...)Choose minimal deletion cost

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

console.log(minimumDeleteSum("sea", "eat")); // 231

Line Notes

const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));Create 2D DP array

dp[i][0] = dp[i-1][0] + s1.charCodeAt(i-1);Initialize first column with deletion costs

if (s1[i-1] === s2[j-1])No cost if chars match

dp[i][j] = Math.min(...)Choose minimal deletion cost

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill a 2D table of size m*n once, each cell computed in O(1).

💡 For strings of length 1000, about 1 million operations, efficient for interviews.

Interview Verdict: Accepted

Tabulation is the preferred approach in interviews for clarity and efficiency.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1], we can optimize space to O(n) by storing only one row at a time.

Intuition

Use a single 1D array to represent the current row, updating it iteratively while preserving needed previous values.

Algorithm

1. Initialize a 1D dp array representing costs for s2 prefixes when s1 is empty.
2. Iterate over s1 characters, updating dp for each s2 prefix.
3. Use a temporary variable to store dp[j-1] from previous iteration (dp[i-1][j-1]).
4. If characters match, copy previous diagonal value; else take min deletion cost.
5. Return dp[n] as final answer.

💡 This approach reduces memory usage while maintaining correctness by iterating backwards over dp array.

Recurrence:dp[j] = if s1[i-1] == s2[j-1] then prevDiagonal else min(dp[j] + ASCII(s1[i-1]), dp[j-1] + ASCII(s2[j-1]))

</>

Code

def minimumDeleteSum(s1: str, s2: str) -> int:
    m, n = len(s1), 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 = dp[0]
        dp[0] += ord(s1[i-1])
        for j in range(1, n + 1):
            temp = dp[j]
            if s1[i-1] == s2[j-1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j] + ord(s1[i-1]), dp[j-1] + ord(s2[j-1]))
            prev = temp
    return dp[n]

# Example usage:
if __name__ == '__main__':
    print(minimumDeleteSum("sea", "eat"))  # Output: 231

Line Notes

dp = [0] * (n + 1)Initialize 1D dp array for s2 prefixes

for j in range(1, n + 1): dp[j] = dp[j-1] + ord(s2[j-1])Base case: cost deleting all s2 chars when s1 empty

prev = dp[0]Store dp[i-1][j-1] before update

dp[j] = min(...)Update dp[j] with minimal deletion cost

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minimumDeleteSum("sea", "eat")); // 231
    }
}

Line Notes

int[] dp = new int[n + 1];1D dp array for s2 prefixes

for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] + s2.charAt(j - 1);Initialize base case

int prev = dp[0];Store previous diagonal value

dp[j] = Math.min(...)Update dp[j] with minimal deletion cost

#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

int main() {
    Solution sol;
    cout << sol.minimumDeleteSum("sea", "eat") << endl; // 231
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);1D dp array for s2 prefixes

for (int j = 1; j <= n; j++) dp[j] = dp[j - 1] + s2[j - 1];Initialize base case

int prev = dp[0];Store previous diagonal value

dp[j] = min(...)Update dp[j] with minimal deletion cost

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

console.log(minimumDeleteSum("sea", "eat")); // 231

Line Notes

const dp = new Array(n + 1).fill(0);Initialize 1D dp array

for (let j = 1; j <= n; j++) dp[j] = dp[j - 1] + s2.charCodeAt(j - 1);Base case initialization

let prev = dp[0];Store previous diagonal value

dp[j] = Math.min(...)Update dp[j] with minimal deletion cost

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single dp array of length n and update it for each character of s1.

💡 This reduces memory usage significantly while maintaining the same time complexity.

Interview Verdict: Accepted

Space optimization is a great follow-up to show deeper understanding of DP.

📊

All Approaches - One-Glance Tradeoffs

💡 Tabulation or memoization are best for interviews; brute force is for understanding; space optimization is a bonus.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(m*n)	O(m*n)	Possible but unlikely for constraints	Yes with extra bookkeeping	Good for quick implementation
3. Bottom-Up Tabulation	O(m*n)	O(m*n)	No	Yes with backtracking	Preferred approach for clarity and efficiency
4. Space Optimized DP	O(m*n)	O(n)	No	Harder, requires extra logic	Mention if asked about optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show understanding of problem structure.Introduce memoization to optimize overlapping subproblems.Present bottom-up tabulation for iterative clarity.Discuss space optimization if time permits.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of string DP, ability to define states and transitions, optimization skills, and clean coding.

Common Follow-ups

• Can you optimize space complexity? → Use 1D DP array
• What if we want to reconstruct the deleted characters? → Store choices in DP or backtrack
• How does this relate to LCS? → Minimum delete sum relates to ASCII sum of non-LCS chars
• What if insertions were allowed? → Problem becomes edit distance variant

💡 These follow-ups test deeper understanding and ability to extend the solution.

🔍

Pattern Recognition

When to Use

1) Problem involves making two strings equal by deletions; 2) Cost depends on characters; 3) Overlapping subproblems exist; 4) Optimal substructure present.

Signature Phrases

'minimum ASCII sum of deleted characters''make two strings equal by deleting characters'

NOT This Pattern When

Problems focusing on substring matching without deletions or problems with only insertions/substitutions

Similar Problems

Delete Operation for Two Strings - similar LCS-based deletion costLongest Common Subsequence - foundational for understanding this problemEdit Distance - generalization with insertions and substitutions

Practice

1. Consider the following Python function implementing the optimal palindrome partitioning min cuts algorithm. What is the returned value when the input string is "aab"?

easy

A. 1

B. 0

C. 2

D. 3

Solution

1. Step 1: Initialize dp array

   dp = [0,1,2] for string "aab" (indices 0 to 2)

2. Step 2: Expand palindromes and update dp

   Center=0: odd palindrome "a" updates dp[0]=0; even palindrome "aa" updates dp[1]=0; Center=1: odd palindrome "a" updates dp[1]=0; Center=2: odd palindrome "b" updates dp[2]=min(2, dp[1]+1)=min(2,0+1)=1

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimum cuts for "aab" is 1 [OK]

Hint: Trace dp updates for palindrome centers carefully [OK]

Common Mistakes:

• Off-by-one errors in dp indexing
• Miscounting cuts for last character
• Ignoring even length palindromes

2. Consider the following Python code for computing the length of the shortest common supersequence of two strings. What is the final returned value when calling scs_length("abac", "cab")?

easy

A. 5

B. 7

C. 6

D. 4

Solution

1. Step 1: Trace dp arrays for i=1 to 4 and j=1 to 3 with str1="abac", str2="cab"

   Initialize prev=[0,1,2,3]. For i=1 ('a'), update curr accordingly comparing with 'c','a','b'.

2. Step 2: Compute final dp row and return prev[n]

   After full iteration, prev[n] = 6, which is the length of the shortest common supersequence.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Manual dp tracing confirms final length is 6 [OK]

Hint: Trace dp arrays carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Off-by-one indexing in loops
• Confusing i,j indices with string indices
• Miscomputing min values in dp

3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the shortest common supersequence problem, where the input strings have lengths m and n?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m^2 + n^2)

Solution

1. Step 1: Identify nested loops over m and n in the DP code

   The outer loop runs m times, inner loop runs n times, each iteration constant work.

2. Step 2: Confirm no extra multiplicative factors from recursion or auxiliary structures

   Space optimization reduces space but does not affect time complexity, which remains O(m*n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table filling requires m*n steps, no hidden extra loops [OK]

Hint: DP with two nested loops over m and n -> O(m*n) time [OK]

Common Mistakes:

• Confusing space with time complexity
• Assuming recursion stack adds multiplicative factor
• Thinking linear time is possible

4. Suppose the regular expression pattern is extended to allow '+' which matches one or more of the preceding element (in addition to '.' and '*'). Which modification to the DP approach correctly handles '+' without increasing time complexity beyond O(m*n)?

hard

A. Modify dp update to require at least one match before repeating for '+', i.e., dp[j] = (prev and match) or (dp[j] and match) but not dp[j - 2] alone, and initialize accordingly

B. Add a separate DP state dimension to track '+' matches explicitly

C. Treat '+' exactly like '*' by copying dp[j] = dp[j] or dp[j - 2] logic

D. Replace '+' with equivalent '.*' in pattern preprocessing

Solution

1. Step 1: Understand '+' semantics

   '+' requires at least one occurrence of preceding element, unlike '*' which allows zero occurrences.

2. Step 2: Adjust DP update logic

   For '+', dp[j] must be true if previous character matched (prev and match) or if repeating the match (dp[j] and match), but not from dp[j - 2] alone which allows zero occurrences.

3. Step 3: Confirm time complexity

   This modification keeps DP table size and iteration unchanged, preserving O(m*n) time complexity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   '+' requires at least one match, so zero occurrence logic must be excluded [OK]

Hint: '+' differs from '*' by disallowing zero occurrences [OK]

Common Mistakes:

• Treating '+' exactly like '*' allowing zero occurrences

5. Suppose the problem is modified so that each integer in nums1 and nums2 can be used multiple times to form uncrossed lines (i.e., reuse allowed). Which of the following algorithmic changes correctly adapts the solution?

hard

A. Modify the DP to consider unlimited reuse by allowing transitions that do not increment both indices simultaneously after a match

B. Change the DP to allow staying on the same index in nums1 or nums2 after a match, effectively converting to a longest common substring problem

C. Use a greedy approach to connect all matching pairs regardless of crossing

D. Use the same DP but allow matching the same indices multiple times by removing the increment of i and j after a match

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means after matching nums1[i] and nums2[j], we can match nums1[i] or nums2[j] again, so indices may not both increment.

2. Step 2: Adapt DP transitions

   The DP must allow transitions that increment only one index or none after a match, unlike classic LCS where both indices increment. This requires modifying the recurrence to consider reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Allowing reuse requires DP transitions that do not always increment both indices [OK]

Hint: Reuse means indices may not both advance after a match [OK]

Common Mistakes:

• Removing increments without adjusting DP
• Confusing reuse with substring problem
• Using greedy approach ignoring crossing