🧶 Beginner-Friendly Guide 'Minimum ASCII Delete Sum for Two Strings' – LeetCode 712 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

You’re given:

• Two strings, s1 and s2.

Your goal:

• Find the lowest total ASCII sum of deleted characters required to make the two strings identical.

Intuition

This problem is a variation of the Longest Common Subsequence (LCS) or Edit Distance problems. The core idea is to decide, for every character pair, whether to keep them or delete them to reach a state where both strings are equal.

We use Dynamic Programming (DP) with memoization to explore these choices:

1. Base Case – If we reach the end of one string, the only way to make the strings equal is to delete all remaining characters in the other string. We sum up their ASCII values and return that as the cost.
2. Match – If the characters s1[i] and s2[j] are the same, it costs us 0 to keep them. We simply move to the next pair of characters.
3. Mismatch – If they don’t match, we have two primary choices:
   • Delete s1[i] (pay its ASCII value) and compare the rest of s1 with the current s2.
   • Delete s2[j] (pay its ASCII value) and compare the current s1 with the rest of s2.
4. Optimization – We always choose the path that yields the minimum sum. By storing the results in a 2‑D array (dp), we avoid recalculating the same sub‑problem multiple times.

Code Blocks

C++ Solution

class Solution {
public:
    int helper(string& s1, string& s2, int i, int j, vector>& dp) {
        int n = s1.size();
        int m = s2.size();

        // If s1 is exhausted, delete remaining characters of s2
        if (i == n) {
            int sum = 0;
            for (int k = j; k > dp(n, vector(m, -1));
        return helper(s1, s2, 0, 0, dp);
    }
};

Python Solution

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        n, m = len(s1), len(s2)
        dp = [[-1] * m for _ in range(n)]

        def helper(i, j):
            # Base case: s1 exhausted
            if i == n:
                return sum(ord(c) for c in s2[j:])
            # Base case: s2 exhausted
            if j == m:
                return sum(ord(c) for c in s1[i:])

            if dp[i][j] != -1:
                return dp[i][j]

            if s1[i] == s2[j]:
                dp[i][j] = helper(i + 1, j + 1)
            else:
                # Compare cost of deleting from s1 vs deleting from s2
                delete_s1 = ord(s1[i]) + helper(i + 1, j)
                delete_s2 = ord(s2[j]) + helper(i, j + 1)
                dp[i][j] = min(delete_s1, delete_s2)

            return dp[i][j]

        return helper(0, 0)

JavaScript Solution

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumDeleteSum = function (s1, s2) {
    const n = s1.length;
    const m = s2.length;
    const dp = Array.from({ length: n }, () => Array(m).fill(-1));

    function helper(i, j) {
        // Base case: s1 exhausted
        if (i === n) {
            let sum = 0;
            for (let k = j; k < m; ++k) sum += s2.charCodeAt(k);
            return sum;
        }
        // Base case: s2 exhausted
        if (j === m) {
            let sum = 0;
            for (let k = i; k < n; ++k) sum += s1.charCodeAt(k);
            return sum;
        }

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

        if (s1[i] === s2[j]) {
            dp[i][j] = helper(i + 1, j + 1);
        } else {
            // Minimum of deleting s1[i] or s2[j]
            const deleteS1 = s1.charCodeAt(i) + helper(i + 1, j);
            const deleteS2 = s2.charCodeAt(j) + helper(i, j + 1);
            dp[i][j] = Math.min(deleteS1, deleteS2);
        }
        return dp[i][j];
    }

    return helper(0, 0);
};

Key Takeaways

• Memoization: By caching results in a 2‑D array, we reduce the time complexity from exponential to O(n · m), where n and m are the lengths of the two strings.
• ASCII Mapping: Character values are not just labels. Using ord() in Python or charCodeAt() in JavaScript lets us treat text as numerical data for optimization.
• Decision Trees: This problem teaches you how to model choices (delete s1 vs. delete s2) as a tree of recursive calls and then prune it efficiently with DP.

Final Thoughts

The Minimum ASCII Delete Sum problem is a classic example of turning a seemingly simple string‑manipulation task into a dynamic‑programming challenge. By understanding the underlying LCS‑style recurrence and applying memoization, you can solve it efficiently in any language.

Minor tweaks to a standard algorithm can change its application. In real‑world software engineering, this logic is used in Bioinformatics to align DNA sequences or in Version Control Systems (e.g., Git) to calculate the diff between two file versions. Mastering these weighted‑string problems will make you much more effective at building search engines or comparison tools.