Maximum Number of Operations to Move Ones to the End

Problem

You are given a binary string s.

You can perform the following operation on the string any number of times:

• Choose any index i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.
• Move the character s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "0** _001_** 10".

Return the maximum number of operations that you can perform.

Examples

Example 1

Input: s = "1001101"

Output: 4

Explanation:

We can perform the following operations:

  * Choose index `i = 0`. The resulting string is `s = "_**001**_ 1101"`.
  * Choose index `i = 4`. The resulting string is `s = "0011 _**01**_ 1"`.
  * Choose index `i = 3`. The resulting string is `s = "001** _01_** 11"`.
  * Choose index `i = 2`. The resulting string is `s = "00** _01_** 111"`.

Example 2

Input: s = "00111"

Output: 0

Constraints

• 1 <= s.length <= 10^5
• s[i] is either '0' or '1'.

Solution

Method 1 – Greedy Forward Counting

Intuition

The key idea is to count, for each '1', how many valid moves it can make by tracking the number of '0's it can pass. As we traverse the string, we accumulate the number of '1's and use a flag to indicate when a '0' allows moves. Each time a '1' is encountered after a '0', all previous '1's can be moved past that '0'.

Approach

1. Initialize result (total moves), ones (count of '1's), and use (flag for available '0').
2. Traverse the string from left to right:
   • If the character is '0', set use to true.
   • If the character is '1':
     • If use is true, add ones to result (all previous '1's can move past this '0').
     • Increment ones.
     • Reset use to false.
3. After traversal, if there are remaining '0's at the end, add the remaining ones to result.
4. Return result.

Complexity

• ⏰ Time complexity: O(n) – We traverse the string once, where $n$ is the length of s.
• 🧺 Space complexity: O(1) – Only a few counters and flags are used.

Code

C++

#include <string>
using namespace std;
class Solution {
public:
    int maxOperations(string s) {
        int result = 0, ones = 0;
        bool use = false;
        for (char c : s) {
            if (c == '0') {
                use = true;
            } else {
                if (use) result += ones;
                ones++;
                use = false;
            }
        }
        if (use) result += ones;
        return result;
    }
};

Go

func maxOperations(s string) int {
    result, ones := 0, 0
    use := false
    for _, c := range s {
        if c == '0' {
            use = true
        } else {
            if use {
                result += ones
            }
            ones++
            use = false
        }
    }
    if use {
        result += ones
    }
    return result
}

Java

class Solution {
    public int maxOperations(String s) {
        int result = 0, ones = 0;
        boolean use = false;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                use = true;
            } else {
                if (use) result += ones;
                ones++;
                use = false;
            }
        }
        if (use) result += ones;
        return result;
    }
}

Kotlin

class Solution {
    fun maxOperations(s: String): Int {
        var result = 0
        var ones = 0
        var use = false
        for (c in s) {
            if (c == '0') {
                use = true
            } else {
                if (use) result += ones
                ones++
                use = false
            }
        }
        if (use) result += ones
        return result
    }
}

Python

class Solution:
    def maxOperations(self, s: str) -> int:
        result = 0
        ones = 0
        use = False
        for c in s:
            if c == '0':
                use = True
            else:
                if use:
                    result += ones
                ones += 1
                use = False
        if use:
            result += ones
        return result

Rust

impl Solution {
    pub fn max_operations(s: String) -> i32 {
        let mut result = 0;
        let mut ones = 0;
        let mut use_flag = false;
        for c in s.chars() {
            if c == '0' {
                use_flag = true;
            } else {
                if use_flag {
                    result += ones;
                }
                ones += 1;
                use_flag = false;
            }
        }
        if use_flag {
            result += ones;
        }
        result
    }
}

TypeScript

class Solution {
    maxOperations(s: string): number {
        let result = 0, ones = 0, use = false;
        for (const c of s) {
            if (c === '0') {
                use = true;
            } else {
                if (use) result += ones;
                ones++;
                use = false;
            }
        }
        if (use) result += ones;
        return result;
    }
}