2167. Minimum Time to Remove All Cars Containing Illegal Goods Hard

1/**
2 * [2167] Minimum Time to Remove All Cars Containing Illegal Goods
3 *
4 * 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.
5 * 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:
6 * <ol>
7 * 	Remove a train car from the left end (i.e., remove s[0]) which takes 1 unit of time.
8 * 	Remove a train car from the right end (i.e., remove s[s.length - 1]) which takes 1 unit of time.
9 * 	Remove a train car from anywhere in the sequence which takes 2 units of time.
10 * </ol>
11 * Return the minimum time to remove all the cars containing illegal goods.
12 * Note that an empty sequence of cars is considered to have no cars containing illegal goods.
13 *  
14 * Example 1:
15 * 
16 * Input: s = "<u>11</u>00<u>1</u>0<u>1</u>"
17 * Output: 5
18 * Explanation: 
19 * One way to remove all the cars containing illegal goods from the sequence is to
20 * - remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
21 * - remove a car from the right end. Time taken is 1.
22 * - remove the car containing illegal goods found in the middle. Time taken is 2.
23 * This obtains a total time of 2 + 1 + 2 = 5. 
24 * An alternative way is to
25 * - remove a car from the left end 2 times. Time taken is 2 * 1 = 2.
26 * - remove a car from the right end 3 times. Time taken is 3 * 1 = 3.
27 * This also obtains a total time of 2 + 3 = 5.
28 * 5 is the minimum time taken to remove all the cars containing illegal goods. 
29 * There are no other ways to remove them with less time.
30 * 
31 * Example 2:
32 * 
33 * Input: s = "00<u>1</u>0"
34 * Output: 2
35 * Explanation:
36 * One way to remove all the cars containing illegal goods from the sequence is to
37 * - remove a car from the left end 3 times. Time taken is 3 * 1 = 3.
38 * This obtains a total time of 3.
39 * Another way to remove all the cars containing illegal goods from the sequence is to
40 * - remove the car containing illegal goods found in the middle. Time taken is 2.
41 * This obtains a total time of 2.
42 * Another way to remove all the cars containing illegal goods from the sequence is to 
43 * - remove a car from the right end 2 times. Time taken is 2 * 1 = 2. 
44 * This obtains a total time of 2.
45 * 2 is the minimum time taken to remove all the cars containing illegal goods. 
46 * There are no other ways to remove them with less time.
47 *  
48 * Constraints:
49 * 
50 * 	1 <= s.length <= 2 * 10^5
51 * 	s[i] is either '0' or '1'.
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/minimum-time-to-remove-all-cars-containing-illegal-goods/
57// discuss: https://leetcode.com/problems/minimum-time-to-remove-all-cars-containing-illegal-goods/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn minimum_time(s: String) -> i32 {
63        0
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_2167() {
75    }
76}
77