FunctionRacerProblemsRace

Lightest Deletions to Match

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems