Class Solution
java.lang.Object
g2101_2200.s2167_minimum_time_to_remove_all_cars_containing_illegal_goods.Solution
2167 - Minimum Time to Remove All Cars Containing Illegal Goods.<p>Hard</p>
<p>You are given a <strong>0-indexed</strong> binary string <code>s</code> which represents a sequence of train cars. <code>s[i] = '0'</code> denotes that the <code>i<sup>th</sup></code> car does <strong>not</strong> contain illegal goods and <code>s[i] = '1'</code> denotes that the <code>i<sup>th</sup></code> car does contain illegal goods.</p>
<p>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 <strong>any</strong> number of times:</p>
<ol>
<li>Remove a train car from the <strong>left</strong> end (i.e., remove <code>s[0]</code>) which takes 1 unit of time.</li>
<li>Remove a train car from the <strong>right</strong> end (i.e., remove <code>s[s.length - 1]</code>) which takes 1 unit of time.</li>
<li>Remove a train car from <strong>anywhere</strong> in the sequence which takes 2 units of time.</li>
</ol>
<p>Return <em>the <strong>minimum</strong> time to remove all the cars containing illegal goods</em>.</p>
<p>Note that an empty sequence of cars is considered to have no cars containing illegal goods.</p>
<p><strong>Example 1:</strong></p>
<p><strong>Input:</strong> s = “<strong>11</strong>00<strong>1</strong>0<strong>1</strong>”</p>
<p><strong>Output:</strong> 5</p>
<p><strong>Explanation:</strong></p>
<p>One way to remove all the cars containing illegal goods from the sequence is to</p>
<ul>
<li>
<p>remove a car from the left end 2 times. Time taken is 2 * 1 = 2.</p>
</li>
<li>
<p>remove a car from the right end. Time taken is 1.</p>
</li>
<li>
<p>remove the car containing illegal goods found in the middle. Time taken is 2. This obtains a total time of 2 + 1 + 2 = 5. An alternative way is to</p>
</li>
<li>
<p>remove a car from the left end 2 times. Time taken is 2 * 1 = 2.</p>
</li>
<li>
<p>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.</p>
</li>
</ul>
<p>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.</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> s = “00<strong>1</strong>0”</p>
<p><strong>Output:</strong> 2</p>
<p><strong>Explanation:</strong> One way to remove all the cars containing illegal goods from the sequence is to</p>
<ul>
<li>remove a car from the left end 3 times. Time taken is 3 * 1 = 3.</li>
</ul>
<p>This obtains a total time of 3.</p>
<p>Another way to remove all the cars containing illegal goods from the sequence is to</p>
<ul>
<li>remove the car containing illegal goods found in the middle. Time taken is 2. This obtains a total time of 2.</li>
</ul>
<p>Another way to remove all the cars containing illegal goods from the sequence is to</p>
<ul>
<li>remove a car from the right end 2 times. Time taken is 2 * 1 = 2.</li>
</ul>
<p>This obtains a total time of 2.</p>
<p>2 is the minimum time taken to remove all the cars containing illegal goods.</p>
<p>There are no other ways to remove them with less time.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= s.length <= 2 * 10<sup>5</sup></code></li>
<li><code>s[i]</code> is either <code>'0'</code> or <code>'1'</code>.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
minimumTime
-