hardDynamic Programming 2DPure DSA~35 min
Minimum Deletion Cost to Make Two Strings Equal
Two text streams must be reduced to a common string by deleting characters. Each deleted character costs its ASCII value. Find the minimum total deletion cost to make the two equal.
Problem
Given two strings s1 and s2, return the lowest ASCII sum of deleted characters needed to make the two strings equal (deleting characters from either string).
Input
Two lowercase strings s1 and s2.
Output
An integer: the minimum total ASCII deletion cost.
Constraints
- 1 <= s1.length, s2.length <= 1000
- s1 and s2 contain only lowercase English letters.
- Cost of deleting a character equals its ASCII value.
Examples
Example 1
Input
s1 = "sea", s2 = "eat"
Output
231
Delete 's' (115) from sea and 't' (116) from eat: 115 + 116 = 231.
Example 2
Input
s1 = "delete", s2 = "leet"
Output
403
Deleting the right characters totals 403 in ASCII cost.