Description
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.
Example 1:
Input: s = "110", k = 1
Output: 1
Explanation:
- There is one
'0'ins. - Since
k = 1, we can flip it directly in one operation.
Example 2:
Input: s = "0101", k = 3
Output: 2
Explanation:
One optimal set of operations choosing k = 3 indices in each operation is:
- Operation 1: Flip indices
[0, 1, 3].schanges from"0101"to"1000". - Operation 2: Flip indices
[1, 2, 3].schanges from"1000"to"1111".
Thus, the minimum number of operations is 2.
Example 3:
Input: s = "101", k = 2
Output: -1
Explanation:
Since k = 2 and s has only one '0', it is impossible to flip exactly k indices to make all '1'. Hence, the answer is -1.
Constraints:
1 <= s.length <= 105s[i]is either'0'or'1'.1 <= k <= s.length
Solutions
This algorithm uses BFS (breadth-first search) to find the minimum number of operations needed to transform a string to all zeros, with constraints based on parameter k. It starts by counting the number of zeros in string s (stored in m), then uses two AVL trees (organized by even/odd indices for efficient lookups) to explore all reachable states. For each state, it calculates a valid range of next states using formulas involving k, and uses the tree's upperBound method to efficiently find all states in that range without checking each one individually. The algorithm tracks the distance to reach each state, proceeding breadth-first so the first time it encounters state 0, it has found the shortest path—or returns -1 if state 0 is unreachable. The clever use of AVL trees avoids repeatedly checking already-visited states, making the search much faster than naive iteration.
const { AvlTree } = require("@datastructures-js/binary-search-tree");
var minOperations = function (s, k) {
const n = s.length;
let m = 0;
const dist = new Array(n + 1).fill(Infinity);
const nodeTrees = [new AvlTree(), new AvlTree()];
for (let i = 0; i <= n; i++) {
nodeTrees[i % 2].insert(i);
if (i < n && s[i] === "0") {
m++;
}
}
const queue = new Array(n + 1);
let head = 0,
tail = 0;
queue[tail++] = m;
dist[m] = 0;
nodeTrees[m % 2].remove(m);
while (head < tail) {
const currentM = queue[head++];
const c1 = Math.max(k - n + currentM, 0);
const c2 = Math.min(currentM, k);
const lnode = currentM + k - 2 * c2;
const rnode = currentM + k - 2 * c1;
const currentTree = nodeTrees[lnode % 2];
let node = currentTree.upperBound(lnode, true);
while (node !== null) {
const nodeValue = node.getValue();
if (nodeValue > rnode) {
break;
}
dist[nodeValue] = dist[currentM] + 1;
queue[tail++] = nodeValue;
const nextNode = currentTree.upperBound(nodeValue, false);
currentTree.remove(nodeValue);
node = nextNode;
}
}
return dist[0] === Infinity ? -1 : dist[0];
};