801. Cheapest Deletions
A printing press prepares two lowercase strings a and b and must make them identical before they go to print. The only allowed operation is to remove a single character from either string, and removing a character costs its ASCII code (so removing a costs 97 and removing z costs 122).
Return the minimum total cost of removals, over both strings, that leaves two equal strings. Both strings may end up empty, which is the outcome when they share no letter.
Aim for O(n*m) time, where n and m are the string lengths, and O(min(n, m)) extra space.
Example 1
- Input:
- a = "moonlit", b = "tonic"
- Output:
- 659
- Explanation:
Keeping the heaviest common subsequence and deleting everything else costs 659 in total.
Example 2
- Input:
- a = "zzaz", b = "azzz"
- Output:
- 194
- Explanation:
Keeping the heaviest common subsequence and deleting everything else costs 194 in total.
Example 3
- Input:
- a = "ferrymen", b = "merry"
- Output:
- 531
- Explanation:
Keeping the heaviest common subsequence and deleting everything else costs 531 in total.
Constraints
1 ≤ a.length, b.length ≤ 1000
Both strings contain only lowercase English letters. The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n*m)
- Space
- O(min(n,m))