🎨Now live: Try our Free AI Image Generation Feature

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 wherei + 1 < s.length
such thats[i] == '1'
ands[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
- Initialize two counters,
cnt
for counting the consecutive '10' pairs andres
for counting the result. - Iterate through the string
s
from the first character to the second-to-last character. - Whenever a '1' is found followed by a '0', increment the
cnt
for possible operations. - Update the result
res
with the count of these operations. - 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;
};