<p>You are given a <span data-keyword="binary-string">binary string</span> <code>s</code>.</p>

<p>You can perform the following operation on the string <strong>any</strong> number of times:</p>

<ul>
	<li>Choose <strong>any</strong> index <code>i</code> from the string where <code>i + 1 &lt; s.length</code> such that <code>s[i] == &#39;1&#39;</code> and <code>s[i + 1] == &#39;0&#39;</code>.</li>
	<li>Move the character <code>s[i]</code> to the <strong>right</strong> until it reaches the end of the string or another <code>&#39;1&#39;</code>. For example, for <code>s = &quot;010010&quot;</code>, if we choose <code>i = 1</code>, the resulting string will be <code>s = &quot;0<strong><u>001</u></strong>10&quot;</code>.</li>
</ul>

<p>Return the <strong>maximum</strong> number of operations that you can perform.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;1001101&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>We can perform the following operations:</p>

<ul>
	<li>Choose index <code>i = 0</code>. The resulting string is <code>s = &quot;<u><strong>001</strong></u>1101&quot;</code>.</li>
	<li>Choose index <code>i = 4</code>. The resulting string is <code>s = &quot;0011<u><strong>01</strong></u>1&quot;</code>.</li>
	<li>Choose index <code>i = 3</code>. The resulting string is <code>s = &quot;001<strong><u>01</u></strong>11&quot;</code>.</li>
	<li>Choose index <code>i = 2</code>. The resulting string is <code>s = &quot;00<strong><u>01</u></strong>111&quot;</code>.</li>
</ul>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">s = &quot;00111&quot;</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>
</div>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 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>

"""
The result is related to sum the partial sums. 

------------
1. Reduction to a simple summation problem.

More precisely, in its very core, the problem ammounts to the following computation:
given arr = [a1, a2, a3, a4], its partial sum is:

partial_sum = [a1, a1 + a2, a1 + a2 + a3, a1 + a2 + a3 + a4]

The sum of partial sum is:

sum(partial_sum) = 4 * a1 + 3 * a2 + 2 * a3 + 1 * a4

In general term, it is:
sum(partial_sum) = n * a1 + (n-1) * a2 + ... + (n - k + 1) * ak + ... + 1 * an
--------------

2. Connection with the problem. We use example 1 to establish intuition, then give the
general rule.

Here s = "1001101", first we notice the tailing ones do not play any role. so we can regard
s by removing the tailing ones: s = ""100110".

There are two ways to do the move:

Option 1. From right to left: 100110 -> 100101 -> 100011 -> 000111. This needs 3 steps.
In other words, we just need to count the consecutive ones separated by zeros. Here 1 + 2 = 3.

Option 2. From left to right: 100110 -> 001110 ->| 001101 -> 001011 -> 00011. This needs 4 steps. It amounts to first accumulate from left, then move to the next blocks of ones, and finally move the full block of ones to the end. Here we have one blocks of size [1, 2]. 
We first move the block of size 1 to the next block, this needs 1 steps, and now we have
a block of ones of size 1 + 2 = 3, [3], then we move this block of size 3 to the next block of ones in the right if any or to the end and mission done. 


To sum up, Option 1 is to compute the sum of block sizes of consecutive ones, while Option 2 is to compuet the sum of the partial sums of block sizes. Obviously, Option 2 yields more steps. 

--------------------

3. Solve the problem. The code itself speaks. We do not repeat the process here.

"""



class Solution:
    def maxOperations(self, s: str) -> int:
        n = len(s)
        
        # trim the tailing ones
        r = n - 1
        while r >= 0 and s[r] == "1":
            r -= 1
        s = s[:r+1]
        
        # find the segments of ones and their lengths
        # one line of code is sufficient. We used two lines for pedagogical purpose
        segments_of_ones = [item for item in s.split("0") if item]
        segments_len = [len(item) for item in segments_of_ones]
        
        # return
        n = len(segments_len)
        return sum([(n - i) * length for i, length in enumerate(segments_len)], 0)
    
        
        
        
19300