Cheapest Deletions, No Equal Neighbours
A string of lowercase letters has a deletion cost for each position. Delete any set of characters, paying their costs, so that the remaining string has no two EQUAL ADJACENT characters. Print the smallest total cost.
abaac, costs 1 2 3 4 5 -> 3 delete the 'a' costing 3
abc, costs 1 2 3 -> 0 already fine
The natural first move is a two-state scan carrying whether the previous character was kept. That works. But the structure collapses further, and seeing why is the content here.
## The observation
Deletions never interact ACROSS different letters. A maximal run of equal characters,
such as the aa inside abaac, must end up with at most one character left, because
any two survivors of the same run would still be adjacent after everything between them
is gone. And runs of different letters never constrain each other, because whatever
survives from one run differs from whatever survives from the next.
So the problem splits into independent runs, and inside a run of length m the cheapest
legal outcome is to keep exactly one character, the MOST EXPENSIVE one:
cost of a run = (sum of its costs) - (largest of its costs)
Total is the sum over runs. A run of length 1 costs 0, which the formula gives for free.
## Why keeping exactly one, and why the dearest
Keeping zero characters from a run is never required: the neighbours of the run are different letters, so one survivor is always legal. Keeping two is never legal. So exactly one survives, and paying the least means keeping the one that would have cost the most to delete.
aaa with costs 5 1 5 answers 6: keep one of the 5s and delete the other 5 and the 1.
That is 11 - 5. Keeping the cheap middle character instead costs 10, and a solution
that keeps the FIRST character of each run reports exactly that.
## What the tests pin down
bbbaaa with costs 4 1 2 3 1 2 answers 6, three from each run, and it is there
because the two runs must be treated separately. A scan that resets its run bookkeeping
only on a deletion, rather than on a change of letter, merges them.
aabbcc answers 3 with costs 1 2 1 2 1 2, one from each of three runs, which catches
an off-by-one in where a run is considered to end.
Costs reach 10^4 over 2 * 10^5 positions, so the total needs 64 bits.