Lightest Deletions to Match
Deleting a letter costs its position in the alphabet: deleting an a costs 1, a b costs 2, and so on up to z, which costs 26. You may delete letters from first and from second as often as you like. Return the smallest total cost that leaves the two strings equal. Both strings may end up empty, and strings that are already equal cost 0.
Example 1
first "cat"
second "bat"
returns 5
Delete the c (cost 3) and the b (cost 2) to leave at in both strings.
Example 2
first "ab"
second "ba"
returns 2
Keeping the b and deleting the a from each string costs 1 + 1 = 2; keeping the a instead would cost 4.
Constraints
0 <= len(first) <= 300 <= len(second) <= 30- Both strings hold lowercase letters only
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Longest Climbing ChainMedium
- Longest Insertion LadderMedium
- Longest Mirror SubsequenceMedium
- Loot Around the Lantern RingMedium
- Lowest Photo WallMedium
- Lucky Toll TripsMedium
- No Double LeapsMedium
- One Forgiven DayMedium