Cheapest Deletions to Match

Medium

You get two strings first and second of lowercase English letters. You may delete any characters from either string; deleting a character costs its ASCII code (a is 97, b is 98, …, z is 122). Delete characters so that the two strings become equal (possibly both empty). Return the smallest total cost of the deletions.

Example 1

first="cat", second="act" → 194

Delete a from both strings, leaving ct. The cost is 97 + 97 = 194. Keeping at instead would mean deleting both cs: 99 + 99 = 198.

Example 2

first="abc", second="xyz" → 657

No letters in common, so everything goes: 97 + 98 + 99 + 120 + 121 + 122 = 657.

Constraints

0 ≤ len(first), len(second) ≤ 1000
Both strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium All Balanced Bracket Strings Medium Fewest Letter Edits Medium Ways to Read a Digit Code Medium Weaving Two Strings Medium

Input

first="cat", second="act"

Expected

Run checks the first 3 tests in your browser. Submit checks all 117 tests on the server, hidden ones included.