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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

1
2
3
4


Input: s = "00111"

Output: 0

Constraints

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

Solution

Method 1 – Greedy Counting

Intuition

Each ‘1’ can be moved to the end by swapping with ‘0’s to its right. The number of operations is the sum of the number of ‘0’s to the right of each ‘1’.

Approach

  1. Traverse the string from right to left, counting the number of ‘0’s seen so far.
  2. For each ‘1’, add the current count of ‘0’s to the answer.
  3. Return the total sum as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    long long maximumOperations(string s) {
        long long ans = 0, zeros = 0;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (s[i] == '0') zeros++;
            else ans += zeros;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func maximumOperations(s string) int64 {
    ans, zeros := int64(0), int64(0)
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '0' {
            zeros++
        } else {
            ans += zeros
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public long maximumOperations(String s) {
        long ans = 0, zeros = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') zeros++;
            else ans += zeros;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun maximumOperations(s: String): Long {
        var ans = 0L
        var zeros = 0L
        for (i in s.length - 1 downTo 0) {
            if (s[i] == '0') zeros++
            else ans += zeros
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def maximumOperations(self, s: str) -> int:
        ans = zeros = 0
        for c in reversed(s):
            if c == '0':
                zeros += 1
            else:
                ans += zeros
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn maximum_operations(s: String) -> i64 {
        let mut ans = 0;
        let mut zeros = 0;
        for c in s.chars().rev() {
            if c == '0' {
                zeros += 1;
            } else {
                ans += zeros;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    maximumOperations(s: string): number {
        let ans = 0, zeros = 0;
        for (let i = s.length - 1; i >= 0; i--) {
            if (s[i] === '0') zeros++;
            else ans += zeros;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s, since we traverse the string once.
  • 🧺 Space complexity: O(1), as we use only a few variables.