712. Minimum ASCII Delete Sum for Two Strings

Minimum ASCII Delete Sum for Two Strings (LeetCode 712) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Edit Distance / Levenshtein Distance) subpattern.

How to solve Minimum ASCII Delete Sum for Two Strings

Minimum ASCII Delete Sum for Two Strings is a Edit Distance problem, part of Dynamic Programming (DP) Patterns. Calculate minimum edit operations to transform one string to another using 2D DP.

Work towards the solution in these steps:

1. Consider using dynamic programming to efficiently explore all possible ways to delete characters from both strings.
2. Think about defining a 2D DP array where each cell represents the minimum ASCII delete sum needed to make substrings of s1 and s2 equal.
3. Focus on how to relate the current state to previous states by comparing characters at the current indices of both strings.

The reference solution runs in O(m * n) time and O(n) space.

The Minimum ASCII Delete Sum for Two Strings solution and editorial walks through the full approach with reference code.

Problem statement

Given two strings s1, s2, find 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] 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.

Note: 0 < s1.length, s2.length <= 1000.

All elements of each string will have an ASCII value in [97, 122].

Topics and companies

Topics: Dynamic Programming.

Reported in interviews at TripleByte.

How to practise Minimum ASCII Delete Sum for Two Strings on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(n) space.

Open Minimum ASCII Delete Sum for Two Strings in the code editor, or read the Minimum ASCII Delete Sum for Two Strings editorial for a worked solution with its approach and complexity analysis.

Where Minimum ASCII Delete Sum for Two Strings sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 2D Array (Edit Distance / Levenshtein Distance) subpattern
• The full DSA patterns sheet

Problems related to Minimum ASCII Delete Sum for Two Strings

Other problems that use the same 2D Array (Edit Distance / Levenshtein Distance) and Dynamic Programming (DP) Patterns techniques:

• Delete Operation for Two Strings — Medium, same subpattern
• Edit Distance — Medium, same subpattern
• Regular Expression Matching — Hard, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern

Minimum ASCII Delete Sum for Two Strings FAQ