#2167
Minimum Time to Remove All Cars Containing Illegal Goods
master · 1640 · lc hard +32 · verified · 42.1% accepted · 703 likes · top 23%
Description
You are given a 0-indexed binary string s representing a sequence of train cars. s[i] = '0' means the ith car carries no illegal goods; s[i] = '1' means it does.
As the conductor, you must eliminate all cars containing illegal goods using any combination of:
- Removing a car from the left end, which takes 1 unit of time.
- Removing a car from the right end, which takes 1 unit of time.
- Removing a car from any other position, which takes 2 units of time.
Return the minimum time needed to remove all cars with illegal goods.
An empty sequence of cars contains no illegal goods.
Example 1:
Input: s = "1100101"
Output: 5
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end. Time taken is 1.
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2 + 1 + 2 = 5.
Example 2:
An alternative way is to
- remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
- remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
This also obtains a total time of 2 + 3 = 5.
Example 3:
5 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.
Example 4:
Input: s = "0010"
Output: 2
Explanation:
One way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
This obtains a total time of 3.
Example 5:
Another way to remove all the cars containing illegal goods from the sequence is to
- remove the car containing illegal goods found in the middle. Time taken is 2.
This obtains a total time of 2.
Example 6:
Another way to remove all the cars containing illegal goods from the sequence is to
- remove a car from the right end 2 times. Time taken is 2 * 1 = 2.
This obtains a total time of 2.
Example 7:
2 is the minimum time taken to remove all the cars containing illegal goods.
There are no other ways to remove them with less time.
Code
1
2
3