3228. Maximum Number of Operations to Move Ones to the End

MediumGreedyStringCounting

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:

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')
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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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:

Keep track of how many '1's we've seen so far (cnt)
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
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:

Variables Setup:
- ans: Accumulates the total number of operations
- cnt: Tracks the number of '1's encountered so far
Single Pass Iteration: We iterate through the string once, examining each character along with its index:
```
for i, c in enumerate(s):
```
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.
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.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

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

1class Solution:
2    def maxOperations(self, s: str) -> int:
3        # Initialize the result and counter for '1's
4        result = 0
5        ones_count = 0
6      
7        # Iterate through each character with its index
8        for index, char in enumerate(s):
9            if char == "1":
10                # Count the number of '1's encountered
11                ones_count += 1
12            elif index > 0 and s[index - 1] == "1":
13                # When we encounter a '0' that follows a '1',
14                # add the count of all previous '1's to the result
15                # This represents moving all previous '1's past this '0'
16                result += ones_count
17      
18        return result
19

1class Solution {
2    public int maxOperations(String s) {
3        // Total number of operations performed
4        int totalOperations = 0;
5      
6        // Count of '1' characters encountered so far
7        int onesCount = 0;
8      
9        // Get the length of the input string
10        int stringLength = s.length();
11      
12        // Iterate through each character in the string
13        for (int i = 0; i < stringLength; i++) {
14            // Current character in the string
15            char currentChar = s.charAt(i);
16          
17            if (currentChar == '1') {
18                // If current character is '1', increment the count of ones
19                onesCount++;
20            } else if (i > 0 && s.charAt(i - 1) == '1') {
21                // If current character is '0' and previous character was '1'
22                // (i.e., we found a transition from '1' to '0')
23                // Add the current count of ones to total operations
24                totalOperations += onesCount;
25            }
26        }
27      
28        // Return the total number of operations
29        return totalOperations;
30    }
31}
32

1class Solution {
2public:
3    int maxOperations(string s) {
4        int totalOperations = 0;  // Total number of operations performed
5        int onesCount = 0;         // Count of '1's encountered so far
6        int stringLength = s.size();
7      
8        for (int i = 0; i < stringLength; ++i) {
9            if (s[i] == '1') {
10                // Increment count when we encounter a '1'
11                ++onesCount;
12            } else if (i > 0 && s[i - 1] == '1') {
13                // When we encounter a '0' that follows a '1' (transition from '1' to '0'),
14                // we can perform operations equal to the number of '1's seen so far
15                totalOperations += onesCount;
16            }
17        }
18      
19        return totalOperations;
20    }
21};
22

1/**
2 * Calculates the maximum number of operations that can be performed on a binary string.
3 * An operation involves moving a '1' to the right past '0's.
4 * 
5 * @param s - A binary string containing only '0's and '1's
6 * @returns The maximum number of operations possible
7 */
8function maxOperations(s: string): number {
9    // Initialize result counter and count of consecutive ones
10    let operationCount: number = 0;
11    let onesCount: number = 0;
12    const stringLength: number = s.length;
13  
14    // Iterate through each character in the string
15    for (let index: number = 0; index < stringLength; index++) {
16        if (s[index] === '1') {
17            // Increment the count of ones encountered
18            onesCount++;
19        } else if (index > 0 && s[index - 1] === '1') {
20            // Found a '0' preceded by '1', indicating end of a group of ones
21            // Add the current count of ones to total operations
22            operationCount += onesCount;
23        }
24    }
25  
26    return operationCount;
27}
28

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

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: