Delete characters from two strings so the remaining common subsequence has the minimum total ASCII deletion cost.
Problem
Given two strings s1 and s2, you may delete characters from either string. Each deleted character adds its ASCII value to the total cost.
Return the minimum possible total ASCII deletion sum needed to make the two strings equal.
Two strings are considered equal if they become exactly the same after deletions.
Notes
- You may delete any number of characters from either string.
- You do not need to preserve original positions beyond maintaining order among remaining characters.
- The goal is to minimize the sum of ASCII values of all deleted characters.
Input Format
- Two strings
s1ands2.
Output Format
- A single integer: the minimum ASCII deletion sum required to make the strings equal.
Constraints
0 <= s1.length, s2.length <= 1000- Strings contain lowercase English letters in the common interview formulation.
- The answer fits in a 32-bit signed integer for standard constraints.
Hints
- Think about what characters can remain in both strings after deletions.
- A dynamic programming table over prefixes can track the minimum cost to equalize suffixes or prefixes.
- It can help to compare the cost of deleting from one side versus matching equal characters.
Input Format
s1: first strings2: second string
Output Format
- Return the minimum total ASCII deletion sum needed to make
s1ands2equal.
Constraints
0 <= |s1|, |s2| <= 1000- Characters are typically lowercase letters in the standard problem setting.
- Use 32-bit integer arithmetic for the final answer.
Example 1
Input
s1 = "sea", s2 = "eat"
Output
231
Explanation
Delete 's' from "sea" and 't' from "eat". The cost is 115 + 116 = 231.
Example 2
Input
s1 = "delete", s2 = "leet"
Output
403
Explanation
One optimal way is to delete 'd' and 'e' from the first string and 'l' from the second string, among other equivalent optimal choices, for a total cost of 403.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.