#712

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum ASCII Delete Sum for Two Strings

This problem focuses on minimizing the ASCII delete sum for two strings by using dynamic programming to find the lowest sum of deleted characters.

string dynamic programming

Problem Statement

You are given two strings, s1 and s2. Your goal is to delete characters from both strings to make them equal, minimizing the ASCII sum of the deleted characters.

For example, with s1 = 'sea' and s2 = 'eat', the optimal solution is to delete 's' from 'sea' and 't' from 'eat', giving a minimum sum of 231. You are required to determine the minimum ASCII delete sum for any two strings following this pattern.

Examples

Example 1

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

Output: 231

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

Deleting "dee" from "delete" to turn the string into "let", 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.

Constraints

1 <= s1.length, s2.length <= 1000
s1 and s2 consist of lowercase English letters.

Solution Approach

Dynamic Programming Approach

Use a 2D dynamic programming table dp, where dp(i, j) stores the minimum ASCII delete sum for s1[i:] and s2[j:]. The transition is based on whether the characters match or not. If they do, no deletion is needed; otherwise, calculate the cost by deleting either character.

State Transition and Recursion

The key idea is to use recursion combined with memoization. For each pair of indices, calculate the minimum ASCII sum by either deleting the character from s1 or s2, then recursively solve for the resulting substrings. This minimizes the problem size progressively.

Optimal Substructure

This problem exhibits optimal substructure, meaning the solution for larger substrings can be constructed by solving smaller subproblems. By solving for subproblems from the base cases and building up, we can efficiently find the minimum sum without redundant recalculations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(m * n), where m and n are the lengths of s1 and s2, respectively. This arises from filling the dp table, which has m rows and n columns. The space complexity is also O(m * n) due to the storage of the dp table.

What Interviewers Usually Probe

Look for an understanding of dynamic programming and state transition techniques.
Evaluate the candidate's ability to break down the problem into smaller subproblems and apply recursion.
Assess how well the candidate handles base cases and memoization in dynamic programming solutions.

Common Pitfalls or Variants

Common pitfalls

Failing to properly handle cases where characters match and not using optimal transitions.
Not managing base cases correctly, leading to incorrect calculations in the dp table.
Ignoring the need for memoization, which can result in exponential time complexity.

Follow-up variants

How would the approach change if the strings contained uppercase characters?
What if the characters in the strings were not restricted to lowercase English letters?
Can you optimize the space complexity by reducing the dp table size?

FAQ

What is the time complexity of the Minimum ASCII Delete Sum for Two Strings problem?

The time complexity is O(m * n), where m and n are the lengths of s1 and s2, respectively, due to the need to fill an m x n dynamic programming table.

What is the key dynamic programming concept used in this problem?

The key concept is state transition, where the problem is broken down into subproblems of calculating the minimum ASCII sum for smaller substrings of s1 and s2.

How does recursion work in the solution?

Recursion is used to calculate the minimum sum for substrings of s1 and s2 by considering whether to delete characters from one or both strings at each step.

What is the role of memoization in solving the Minimum ASCII Delete Sum problem?

Memoization helps store intermediate results to avoid redundant recalculations and significantly improves the efficiency of the solution.

Can the space complexity of the Minimum ASCII Delete Sum problem be optimized?

Yes, by optimizing the dynamic programming table, such as using only two rows or applying space-saving techniques, the space complexity can be reduced from O(m * n) to O(min(m, n)).

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the minimum sum of ASCII values of deleted characters required to make the first $i$ characters of $s_1$ equal to the first $j$ characters of $s_2$. The answer is $f[m][n]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        f = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            f[i][0] = f[i - 1][0] + ord(s1[i - 1])
        for j in range(1, n + 1):
            f[0][j] = f[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]:
                    f[i][j] = f[i - 1][j - 1]
                else:
                    f[i][j] = min(
                        f[i - 1][j] + ord(s1[i - 1]), f[i][j - 1] + ord(s2[j - 1])
                    )
        return f[m][n]

Continue Practicing

#730 count different palindromic subsequences #691 stickers to spell word #678 valid parenthesis string