Dare2Solve
You are given a binary string s
. You can perform the following operation on the string any number of times:
i
from the string where i + 1 < s.length
such that s[i] == '1'
and s[i + 1] == '0'
.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.
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.
cnt
for counting the consecutive '10' pairs and res
for counting the result.s
from the first character to the second-to-last character.cnt
for possible operations.res
with the count of these operations.res
after iterating through the string.s
. This is because we traverse the string once.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;
}
};
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
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;
}
}
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;
};