Uncouple the Faulty Wagons

Hard

A train is described by a string wagons of 0s and 1s: wagons[i] = '1' means the i-th wagon is faulty, and '0' means it is fine. Every faulty wagon has to go. Three actions are available, each as many times as you like: - detach the first wagon of the train, costing 1 time unit; - detach the last wagon of the train, costing 1 time unit; - pull any wagon out of the middle, costing 2 time units. Return the least time needed to get rid of every faulty wagon. An empty train counts as having no faulty wagons.

Example 1

wagons='0100110' → 5

Detach two wagons from the left end (2) and three from the right end (3) for a total of 5. Pulling the three faulty ones out of the middle would cost 6.

Example 2

wagons='0001000' → 2

The single faulty wagon is cheapest to pull out of the middle, for 2.

Example 3

wagons='000' → 0

There are no faulty wagons, so nothing needs doing.

Constraints

1 ≤ len(wagons) ≤ 2·10⁵
wagons[i] is '0' or '1'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Does the Text Fit the Pattern Hard Shuffle by Cutting and Swapping Hard Ways to Cross Out Hard

Input

wagons='0100110'

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.