Minimum ASCII Delete Sum for Two Strings
Medium · Dynamic Programming · String · Dynamic Programming
Problem
You are given two strings s1 and s2. You may delete characters from either string, and each deletion costs the ASCII code of the deleted character ('a' is 97, 'z' is 122).
Return the smallest total cost that makes the two strings equal.
Examples
Input: s1 = "cab", s2 = "acb" Output: 194
Delete 'a' from each string (97 + 97) so both become "cb".
Input: s1 = "zz", s2 = "z" Output: 122
Delete one 'z' (122) from the first string.
Input: s1 = "delete", s2 = "leet" Output: 403
Keep "let": delete d, e from the first string (100 + 101 + 101) and e from the second (101), 403 in all.
Constraints
- 1 <= len(s1), len(s2) <= 1000
- s1 and s2 consist of lowercase English letters.
Approaches
- Heaviest common subsequence, then subtract — time O(m * n), space O(m * n)
Follow-up
Nothing in the table depends on the costs being ASCII codes: any price per letter works the same way. The use cases replace the codes with a price list and add a third string, which adds a dimension to the table.
Related problems
Start free on Cariara · Coding problems · System design studio
