Cheapest Trim of Repeats
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
0 <= len(s) <= 60len(costs) == len(s)shas lowercase letters only0 <= costs[i] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.