Minimum ASCII Delete Sum for Two Strings - Video Solutions

Problem Overview: You are given two strings s1 and s2. Delete characters from either string so both become equal while minimizing the total ASCII value of deleted characters. The goal is not the number of deletions but the minimum sum of ASCII values removed.

Approach 1: Recursion with Memoization (Time: O(m*n), Space: O(m*n))

This approach models the problem as a recursive comparison of suffixes from both strings. At position i in s1 and j in s2, you either keep the characters if they match or delete one of them. If s1[i] == s2[j], move both pointers forward with no cost. Otherwise, try deleting s1[i] or s2[j] and add their ASCII values to the total cost. Store results for each state (i, j) in a memo table to avoid recomputation. Without memoization the recursion becomes exponential; caching reduces it to O(m*n). This approach clearly exposes the decision process and is useful when reasoning about overlapping subproblems in dynamic programming.

Approach 2: Dynamic Programming (Bottom-Up) (Time: O(m*n), Space: O(m*n))

The iterative DP solution builds a table dp[i][j] representing the minimum ASCII delete sum required to make s1[i:] and s2[j:] equal. Initialize the last row and column by deleting all remaining characters from the other string, accumulating ASCII values. Then iterate backward through both strings. If characters match, copy the value from dp[i+1][j+1]. If they differ, compute the minimum between deleting from s1 (ASCII(s1[i]) + dp[i+1][j]) or deleting from s2 (ASCII(s2[j]) + dp[i][j+1]). The final answer is dp[0][0]. This formulation is similar to the weighted version of the longest common subsequence problem and relies heavily on string comparison and dynamic programming state transitions.

The DP interpretation can also be viewed as maximizing the ASCII value of the common subsequence shared by both strings. Instead of explicitly building the subsequence, the algorithm directly computes the minimum cost of deletions. The bottom-up version avoids recursion overhead and is usually the most predictable implementation in interviews and production code.

Recommended for interviews: The bottom-up dynamic programming approach is the expected solution. It demonstrates clear state definition (dp[i][j]), correct transitions, and optimal O(m*n) complexity. Starting with the recursive memoized version shows understanding of the subproblem structure, but converting it into an iterative DP table signals stronger problem-solving maturity.