Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

One operation moves a one across an entire consecutive block of zeros, not just one zero. To maximize operations, let earlier ones cross each zero block before allowing neighboring zero blocks to merge. Each original zero block can then contribute one operation for every one originally to its left.

Approach

Scan left to right while counting the ones seen. When a zero is encountered, skip its whole consecutive zero run and add the current number of ones to the answer once. Continue until the string ends.

This sum is achievable by processing zero blocks from left to right and moving preceding ones across the current block from rightmost to leftmost. A one cannot cross the same original zero block twice, and merging blocks only combines crossings into fewer operations, so the count is also an upper bound. Leading zeros add zero, and a long zero run still contributes only once per preceding one.

class Solution:
    def maxOperations(self, s: str) -> int:
        n = len(s)
        ones = 0
        res = 0

        i = 0
        while i < n:
            if s[i] == '0':
                while i < n and s[i] == '0': i += 1
                res += ones
            else:
                ones += 1
                i += 1
        
        return res

Complexity analysis

Let n = s.length. Time: O(n). Auxiliary space: O(1).