Minimum Time to Remove All Cars Containing Illegal Goods
You are given a 0-indexed binary string s which represents a sequence of train cars. s[i] = '0' denotes that the i^th car does not contain illegal goods and s[i] = '1' denotes that the i^th car does contain illegal goods.
As the train conductor, you would like to get rid of all the cars containing illegal goods. You can do any of the following three operations any number of times:
- Remove a train car from the left end (i.e., remove
s[0]), which takes 1 unit of time. - Remove a train car from the right end (i.e., remove
s[s.length - 1]), which takes 1 unit of time. - Remove a train car from anywhere in the sequence, which takes 2 units of time.
Return the minimum time to remove all the cars containing illegal goods.
Note that an empty sequence of cars is considered to have no cars containing illegal goods.
Example 1
Input
s = "1100101"Output
5Removing two cars from the left, one from the right, and the remaining illegal car from the middle takes 5 time units, which is minimum.
Example 2
Input
s = "0010"Output
2Removing the illegal car from the middle or removing two cars from the right both take 2 time units, which is minimum.
Constraints
- 1 <= s.length <= 2 * 10^5
- s[i] is either '0' or '1'.