Problem Description

You are given a binary string s consisting of only '0's and '1's.

You can perform a specific operation on the string any number of times. The operation works as follows:

1. Find any index i in the string where:

   • i + 1 < s.length (there's at least one character after position i)
   • s[i] == '1' (the character at position i is '1')
   • s[i + 1] == '0' (the character at position i + 1 is '0')

2. Move the '1' at position i to the right, sliding it past consecutive '0's until it either:

   • Reaches the end of the string, or
   • Encounters another '1'

For example, if s = "010010" and you choose i = 1 (where there's a '1' followed by '0'), the '1' at index 1 moves right past the '0's at indices 2 and 3, stopping before the '1' at index 4. The result would be s = "000110".

Your task is to find the maximum number of operations you can perform on the string.

The key insight is that each '1' can potentially move multiple times, and you want to count the total number of individual moves (operations) possible across all '1's in the string. Each time a '1' moves past a group of '0's, it counts as one operation.

Intuition

Let's think about what happens when we perform these operations. Each '1' can only move to the right, and it stops when it hits another '1' or reaches the end. The key observation is that '1's will eventually cluster together on the right side of the string.

Consider what triggers an operation: we need a '1' followed by a '0'. When we move this '1' to the right past some '0's, it creates an opportunity for any '1's to its left to also move right in subsequent operations.

Let's trace through an example: s = "11010".

• Initially, the '1' at index 2 can move right (operation 1)
• After moving: "11001", now the '1' at index 1 can move (operation 2)
• After moving: "10101", now the '1' at index 0 can move (operation 3)
• After moving: "01101", now the '1' at index 2 can move again (operation 4)
• And so on...

The pattern that emerges is: whenever we encounter a group of '0's after some '1's, each of those preceding '1's will eventually be able to "jump over" this group of '0's exactly once. If we have cnt number of '1's before a group of '0's, then we can perform cnt operations to move all those '1's past this group.

This leads to a simple counting strategy:

1. Keep track of how many '1's we've seen so far (cnt)
2. When we encounter the end of a group of '0's (which happens when we see a '0' that was preceded by a '1'), we know that all cnt previous '1's can move past this group
3. Add cnt to our answer

The elegance of this approach is that we don't need to simulate the actual movements. We just need to identify where groups of '0's end (by checking if the previous character was '1' when we see a '0') and count how many '1's can move past each group.

Learn more about Greedy patterns.

Solution Approach

The implementation uses a greedy approach with two variables to efficiently count the maximum operations:

1. Variables Setup:

   • ans: Accumulates the total number of operations
   • cnt: Tracks the number of '1's encountered so far

2. Single Pass Iteration: We iterate through the string once, examining each character along with its index:

   for i, c in enumerate(s):

3. Counting Logic:

   • When we see a '1': Increment cnt by 1

     if c == "1":
         cnt += 1

   • When we see a '0' that follows a '1': This marks the end of a segment where '1's can move. We check this condition with:

     elif i and s[i - 1] == "1":
         ans += cnt

     The condition i and s[i - 1] == "1" ensures:

     • We're not at the first position (i is non-zero)
     • The previous character was '1'

     When this condition is met, all cnt number of '1's before this position can eventually move past this group of '0's, so we add cnt to our answer.

4. Why This Works:

   • Each group of consecutive '0's that comes after '1's represents a "barrier" that those '1's can cross
   • We only count operations when we detect the transition from '1' to '0' (the start of a '0' group)
   • The algorithm correctly handles multiple groups of '0's because each group will be counted separately when we encounter its beginning

The time complexity is O(n) where n is the length of the string, as we make a single pass. The space complexity is O(1) as we only use two variables regardless of input size.

Example Walkthrough

Let's walk through the solution with s = "1100110":

Initial state: ans = 0, cnt = 0

Step 1: Index 0, character '1'

• Since it's a '1', increment cnt = 1
• State: ans = 0, cnt = 1

Step 2: Index 1, character '1'

• Since it's a '1', increment cnt = 2
• State: ans = 0, cnt = 2

Step 3: Index 2, character '0'

• It's a '0' and the previous character s[1] = '1'
• This marks the start of a group of '0's that the 2 previous '1's can move past
• Add cnt to answer: ans = 0 + 2 = 2
• State: ans = 2, cnt = 2

Step 4: Index 3, character '0'

• It's a '0' but the previous character s[2] = '0' (not '1')
• No operation counted here (we're in the middle of a '0' group)
• State: ans = 2, cnt = 2

Step 5: Index 4, character '1'

• Since it's a '1', increment cnt = 3
• State: ans = 2, cnt = 3

Step 6: Index 5, character '1'

• Since it's a '1', increment cnt = 4
• State: ans = 2, cnt = 4

Step 7: Index 6, character '0'

• It's a '0' and the previous character s[5] = '1'
• This marks another group of '0's that all 4 '1's seen so far can move past
• Add cnt to answer: ans = 2 + 4 = 6
• State: ans = 6, cnt = 4

Final Answer: 6

This matches what would happen if we actually performed the operations:

• The 2 '1's at the beginning can each move past the first group of '0's (2 operations)
• All 4 '1's (the original 2 plus the 2 in the middle) can each move past the final '0' (4 operations)
• Total: 2 + 4 = 6 operations

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through the string exactly once using a single for loop with enumerate, performing constant-time operations (comparisons and arithmetic operations) at each iteration.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space with variables ans, cnt, i, and c, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Miscounting Operations for Consecutive Zeros

The Problem: A common mistake is counting operations for every '0' in the string rather than just counting once per group of consecutive '0's. For example, in the string "11000", some might incorrectly count 6 operations (2 '1's × 3 '0's) instead of the correct answer of 2 operations (2 '1's × 1 group of '0's).

Why It Happens: The misunderstanding stems from thinking each '0' represents a separate operation, when actually a '1' slides past an entire group of '0's in a single operation.

The Fix: Only count operations when detecting the transition from '1' to '0' (the start of a zero group), not for every '0':

# WRONG: Counts every '0' after '1's
for i, c in enumerate(s):
    if c == "1":
        cnt += 1
    else:  # This counts EVERY '0'
        ans += cnt

# CORRECT: Only counts at the start of each '0' group
for i, c in enumerate(s):
    if c == "1":
        cnt += 1
    elif i and s[i - 1] == "1":  # Only when transitioning from '1' to '0'
        ans += cnt

Pitfall 2: Resetting the '1' Counter

The Problem: Another mistake is resetting the ones_count variable after encountering a group of '0's, thinking that '1's can't move past other '1's.

Why It Happens: Misinterpreting the problem to mean that once '1's move, they can't contribute to future operations.

The Fix: Keep accumulating the '1' count throughout the iteration. Each '1' can potentially contribute to multiple operations as it encounters different groups of '0's:

# WRONG: Resetting counter after each operation
for i, c in enumerate(s):
    if c == "1":
        cnt += 1
    elif i and s[i - 1] == "1":
        ans += cnt
        cnt = 0  # DON'T reset!

# CORRECT: Keep accumulating
for i, c in enumerate(s):
    if c == "1":
        cnt += 1
    elif i and s[i - 1] == "1":
        ans += cnt  # cnt maintains its value for future groups

Pitfall 3: Index Boundary Check

The Problem: Forgetting to check if i > 0 before accessing s[i - 1] can cause an index error or incorrect logic.

Why It Happens: When focusing on the main logic, it's easy to overlook boundary conditions.

The Fix: Always include the index check when looking at previous characters:

# WRONG: No boundary check
elif s[i - 1] == "1":  # Can fail when i = 0
    ans += cnt

# CORRECT: Proper boundary check
elif i and s[i - 1] == "1":  # Short-circuits when i = 0
    ans += cnt