Problem Statement in English

You’re given a binary string s consisting of only ‘0’s and ‘1’s. In one operation, you can select any ‘1’ that has a ‘0’ immediately to its right and move that ‘1’ to the end of the string, or upto the first ‘1’ that hou encounter on the way to the end. Y

our task is to determine the maximum number of such operations that can be performed on the string s.

Approach

If you do a dry run you’ll see that the solution is simply the number of segmeents of continuous ‘0’s that you encounter while traversing the string from right to left, each time you encounter a ‘1’ you can add the number of ‘0’s you’ve seen so far to the result.

Solution in Python


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

        if s[-1] == "0":
            nz += 1

        for i in reversed(range(len(s) - 1)):
            if s[i] == "0" and s[i + 1] != "0":
                nz += 1
            elif s[i] == "1":
                res += nz

        return res

Complexity

  • Time: $O(n)$
    Since we iterate through the string once.

  • Space: $O(1)$
    Since we use only a constant amount of extra space.

Mistakes I Made

I had to watch NeetCode’s video

And we are done.