3666. Minimum Operations to Equalize Binary String
You are given a binary string s, and an integer k.
In one operation, you must choose exactly k different indices and flip each '0' to '1' and each '1' to '0'.
Return the minimum number of operations required to make all characters in the string equal to '1'. If it is not possible, return -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| class Solution {
public:
int minOperations(string s, int k) {
int now = std::count(s.begin(), s.end(), '1');
int n = s.length();
if(now == n) return 0;
if(k % 2 == 0) {
if((now ^ n) & 1) return -1;
}
set<int> st[2];
if(k % 2 == 0) {
for(int i = now & 1; i <= n; i += 2) st[i&1].insert(i);
} else for(int i = 0; i <= n; i++) st[i&1].insert(i);
queue<int> q;
int res = 1, fl = k & 1;
q.push(now);
st[now&1].erase(now);
while(q.size()) {
int qsz = q.size();
while(qsz--) {
int x = q.front(); q.pop();
int until = abs((n - x) - k);
int del = -1;
int xbit = x & 1;
int target = fl ? !xbit : xbit;
for(auto it = st[target].lower_bound(abs(x - k)); it != end(st[target]); it++) {
if(*it > x + k) break;
if(n - *it < until) break;
int bit = (*it ^ x) & 1;
if(del != -1) {
st[target].erase(del);
del = -1;
}
q.push(*it);
del = *it;
if(*it == n) return res;
}
if(del != -1) {
st[target].erase(del);
del = -1;
}
}
res++;
}
return -1;
}
};
|
