<p>You are given a <strong>0-indexed</strong> binary string <code>s</code> which represents a sequence of train cars. <code>s[i] = &#39;0&#39;</code> denotes that the <code>i<sup>th</sup></code> car does <strong>not</strong> contain illegal goods and <code>s[i] = &#39;1&#39;</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>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;<strong><u>11</u></strong>00<strong><u>1</u></strong>0<strong><u>1</u></strong>&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
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. 

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.

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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;00<strong><u>1</u></strong>0&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong>
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.

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.

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.

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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def minimumTime(self, s: str) -> int:
        # tried some stuff, didn't work, let's try again

        # wlog have to delete every 1
        #
        # so we have to
        #     delete it from the left
        #     delete it from the right
        #     or delete it random access

        # there's some window of ones, potentially empty, that we delete by random access
        # left and right will be deleted from the ends

        # cost to delete k ones random access is k plus l/r cost for the prior and next ones, if any

        # 10011010110011001001110011011010001000110010100110010001111110100101011000101110011111101

        # Lee215 to the rescue again
        
        # IMO not very well explained as usual, but he's doing the DP solution I wanted to do in one shot

        # ---------- ------------------- -------------
        #   left           middle             right

        # to delete all ones in left and middle:
        #     delete left in |left| ops
        #     then delete middle ones with 2 each
        #     if at any point |left| + 2*#middleOnes > i+1, just do i+1 instead
        #
        # because the options are delete all the prior ones with left_middle ops, or just delete i+1 indices

        # then we delete the right ones by deleting all of right
        # this might include a bunch of zeros for some i
        # but it doesn't matter because we'll have this as an iteration:
        # -------------- ------------0 11111101
        #           left middle      i
        #    so among all of the middle ones we'll pick up the correct one

        N = len(s)

        left = 0 # total cost to delete zeros in 0..i, mix of deleting from left and middle
        ans = len(s) # dummy value
        for i, c in enumerate(s):
            left = min(left + 2 * (c == '1'), i+1) # delete this random access, or extend L to i
            ans = min(ans, left + N-i-1)

        return ans
18900