Cheapest Deletions to Match

Medium2-D Dynamic Programming

Problem

You may delete characters from two strings first and second. Deleting a character costs its character code (for lowercase letters, a = 97 up to z = 122).

Return the minimum total cost of deletions that makes the two strings identical.

Example 1

Input:
first = "toy", second = "yot"
Output:
454

Keep only "y": delete "t" and "o" from both strings, 2 · (116 + 111) = 454. Keeping "o" would cost 2 · (116 + 121) = 474.

Example 2

Input:
first = "cab", second = "cba"
Output:
194

Keep "cb": delete one "a" from each string, 97 + 97.

Constraints

  • 0 ≤ first.length, second.length ≤ 1000
  • Both strings contain lowercase English letters only.

Hint

Show the first hint

With unit costs this would be m + n - 2 · LCS. Why does that formula break with weighted costs?

Walkthrough

How to approach it

01Clarify before coding

  • Is the cost the ASCII code of the character? Yes, ord(ch) in Python, charCodeAt in JavaScript.
  • Can both strings end up empty? Yes; that costs the sum of all codes.
  • Is it fine to keep any common subsequence, not necessarily the longest? Yes, only the total cost matters.

02Brute force

Enumerate every subsequence to keep in first, check whether second contains it, and price the deletions.

Cost: O(2^m · n): exponential.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.