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.

Intuition

The problem essentially revolves around counting how many '10' pairs can be found and transformed in the string. Each '10' can be turned into '01', making a shift operation possible. We need to count all such pairs to determine the maximum number of operations.

Approach

1. Initialize two counters, cnt for counting the consecutive '10' pairs and res for counting the result.
2. Iterate through the string s from the first character to the second-to-last character.
3. Whenever a '1' is found followed by a '0', increment the cnt for possible operations.
4. Update the result res with the count of these operations.
5. Return the result res after iterating through the string.

Complexity

• Time Complexity: O(n), where n is the length of the string s. This is because we traverse the string once.
• Space Complexity: O(1), as we use a fixed amount of space for the counters regardless of the input size.

Code

C++

class Solution {
public:
    int maxOperations(string s) {
        int cnt = 0;
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '1') ++cnt;
            else if (i > 0 && s[i - 1] == '1') res += cnt;
        }
        return res;
    }
};

Python

class Solution:
    def maxOperations(self, s: str) -> int:
        cnt = 0
        res = 0
        for i in range(len(s)):
            if s[i] == '1':
                cnt += 1
            elif i > 0 and s[i - 1] == '1':
                res += cnt
        return res

Java

class Solution {
    public int maxOperations(String s) {
        int cnt = 0;
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') ++cnt;
            else if (i > 0 && s.charAt(i - 1) == '1') res += cnt;
        }
        return res;
    }
}

JavaScript

var maxOperations = function (s) {
    var cnt = 0;
    var res = 0;
    for (var i = 0; i < s.length; ++i) {
        if (s[i] === "1") ++cnt;
        else if (s[i - 1] === "1") res += cnt;
    }
    return res;
};