Skip to content

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

Description

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 = "000110".

Return the maximum number of operations that you can perform.

 

Example 1:

Input: s = "1001101"

Output: 4

Explanation:

We can perform the following operations:

  • Choose index i = 0. The resulting string is s = "0011101".
  • Choose index i = 4. The resulting string is s = "0011011".
  • Choose index i = 3. The resulting string is s = "0010111".
  • Choose index i = 2. The resulting string is s = "0001111".

Example 2:

Input: s = "00111"

Output: 0

 

Constraints:

  • 1 <= s.length <= 105
  • s[i] is either '0' or '1'.

Solutions

Solution 1: Greedy

We use a variable $\textit{ans}$ to record the answer and another variable $\textit{cnt}$ to count the current number of $1$s.

Then, we iterate through the string $s$. If the current character is $1$, then we increment $\textit{cnt}$. Otherwise, if there is a previous character and the previous character is $1$, then the previous $\textit{cnt}$ number of $1$s can be moved backward, and we add $\textit{cnt}$ to the answer.

Finally, we return the answer.

The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.

1
2
3
4
5
6
7
8
9
class Solution:
    def maxOperations(self, s: str) -> int:
        ans = cnt = 0
        for i, c in enumerate(s):
            if c == "1":
                cnt += 1
            elif i and s[i - 1] == "1":
                ans += cnt
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int maxOperations(String s) {
        int ans = 0, cnt = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '1') {
                ++cnt;
            } else if (i > 0 && s.charAt(i - 1) == '1') {
                ans += cnt;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxOperations(string s) {
        int ans = 0, cnt = 0;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                ++cnt;
            } else if (i && s[i - 1] == '1') {
                ans += cnt;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func maxOperations(s string) (ans int) {
    cnt := 0
    for i, c := range s {
        if c == '1' {
            cnt++
        } else if i > 0 && s[i-1] == '1' {
            ans += cnt
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function maxOperations(s: string): number {
    let [ans, cnt] = [0, 0];
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        if (s[i] === '1') {
            ++cnt;
        } else if (i && s[i - 1] === '1') {
            ans += cnt;
        }
    }
    return ans;
}

Comments