FunctionRacerProblemsRace

Cheapest Trim of Repeats

EasyGreedyPython, JavaScript, TypeScript, Java, C++

s is a string of lowercase letters and costs[i] is the price of deleting s[i]. Delete letters so that no two neighbouring letters in what remains are the same, paying the price of every letter you delete.

Return the smallest total price. The smallest total is unique, so no tie rule is needed. Return 0 when s is empty or already has no two equal neighbours.

Example 1

s "abaac"
costs [1,2,3,4,5]
returns 3

The only repeat is aa at positions 2 and 3; deleting the cheaper one costs 3.

Example 2

s "aabaa"
costs [1,2,3,4,1]
returns 2

The first aa costs 1 + 2 and keeps the 2; the last aa costs 4 + 1 and keeps the 4: 1 + 1 = 2.

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 Greedy problems