1class Solution {
2    public int minOperations(String s, int k) {
3        int n = s.length();
4
5        // Two TreeSets partitioned by parity (even/odd indices).
6        // They store all the "unvisited" zero-count states from 0 to n.
7        // Splitting by parity lets us query a parity-consistent range quickly.
8        @SuppressWarnings("unchecked")
9        TreeSet<Integer>[] unvisited = new TreeSet[2];
10        Arrays.setAll(unvisited, i -> new TreeSet<>());
11
12        // Initialize every possible zero-count value [0, n] as unvisited,
13        // placed into the bucket matching its parity.
14        for (int i = 0; i <= n; i++) {
15            unvisited[i % 2].add(i);
16        }
17
18        // Count the number of '0' characters in the input string (start state).
19        int zeroCount = 0;
20        for (char c : s.toCharArray()) {
21            if (c == '0') {
22                zeroCount++;
23            }
24        }
25
26        // Mark the starting state as visited and enqueue it for BFS.
27        unvisited[zeroCount % 2].remove(zeroCount);
28
29        Deque<Integer> queue = new ArrayDeque<>();
30        queue.offer(zeroCount);
31
32        // BFS level by level; each level represents one operation.
33        int operations = 0;
34        while (!queue.isEmpty()) {
35            for (int size = queue.size(); size > 0; --size) {
36                int current = queue.poll();
37
38                // Reaching zero '0's means the string is all '1's: done.
39                if (current == 0) {
40                    return operations;
41                }
42
43                // Compute the reachable range of next zero-count states.
44                // Lower bound: flip as many zeros to ones as possible.
45                int low = current + k - 2 * Math.min(current, k);
46                // Upper bound: constrained by how many ones can be flipped to zeros.
47                int high = current + k - 2 * Math.max(k - n + current, 0);
48
49                // All reachable states in [low, high] share the same parity as 'low',
50                // so we only need to scan the matching parity bucket.
51                TreeSet<Integer> bucket = unvisited[low % 2];
52
53                // Pull every unvisited state within [low, high], visit and enqueue it.
54                Integer next = bucket.ceiling(low);
55                while (next != null && next <= high) {
56                    queue.offer(next);
57                    bucket.remove(next);
58                    next = bucket.ceiling(low);
59                }
60            }
61            operations++;
62        }
63
64        // No sequence of operations reaches the all-ones state.
65        return -1;
66    }
67}
68

1class Solution {
2public:
3    int minOperations(string s, int k) {
4        int n = s.size();
5
6        // unvisitedStates[parity] holds all reachable counts of '0' that share
7        // the same parity (even/odd). We split by parity because one operation
8        // changes the count of zeros by an even amount (see derivation below),
9        // so the parity of the zero-count is preserved across operations.
10        set<int> unvisitedStates[2];
11        for (int i = 0; i <= n; i++) {
12            unvisitedStates[i % 2].insert(i);
13        }
14
15        // Initial number of '0' characters in the string.
16        int initialZeros = count(s.begin(), s.end(), '0');
17
18        // Remove the starting state since we begin our BFS from it.
19        unvisitedStates[initialZeros % 2].erase(initialZeros);
20
21        // BFS over the possible "number of zeros" states. Each level of the
22        // BFS corresponds to one additional operation applied.
23        queue<int> bfsQueue;
24        bfsQueue.push(initialZeros);
25
26        int operations = 0;
27
28        while (!bfsQueue.empty()) {
29            // Process every state belonging to the current BFS level.
30            for (int levelSize = bfsQueue.size(); levelSize > 0; --levelSize) {
31                int currentZeros = bfsQueue.front();
32                bfsQueue.pop();
33
34                // Goal reached: zero '0' characters remain.
35                if (currentZeros == 0) {
36                    return operations;
37                }
38
39                // In a single operation we flip k characters. Suppose among the
40                // k chosen positions there are x '0's flipped to '1' and (k - x)
41                // '1's flipped to '0'. The new zero-count becomes:
42                //     newZeros = currentZeros - x + (k - x)
43                //              = currentZeros + k - 2 * x
44                //
45                // x ranges over the feasible number of zeros we can pick:
46                //   - At most min(currentZeros, k) zeros can be flipped.
47                //   - We must also flip enough ones; the number of ones is
48                //     (n - currentZeros), so (k - x) <= (n - currentZeros),
49                //     which gives x >= k - (n - currentZeros) = k - n + currentZeros.
50                //   - x cannot be negative, so the lower bound is max(0, k-n+currentZeros).
51                //
52                // Plugging the extreme values of x into newZeros gives the
53                // inclusive range [low, high] of reachable zero-counts:
54                int low  = currentZeros + k - 2 * min(currentZeros, k);
55                int high = currentZeros + k - 2 * max(k - n + currentZeros, 0);
56
57                // All reachable states in [low, high] share parity low % 2.
58                auto& states = unvisitedStates[low % 2];
59
60                // Visit every unvisited state within [low, high].
61                auto it = states.lower_bound(low);
62                while (it != states.end() && *it <= high) {
63                    bfsQueue.push(*it);
64                    it = states.erase(it);  // mark as visited to avoid revisiting
65                }
66            }
67            // One full level processed => one more operation used.
68            operations++;
69        }
70
71        // Unreachable: no sequence of operations reduces zeros to 0.
72        return -1;
73    }
74};
75

1import { AvlTree } from '@datastructures-js/binary-search-tree';
2
3/**
4 * Computes the minimum number of operations needed to reduce the
5 * zero-count of the string to 0, where each operation transforms the
6 * current zero-count into any value within a derived range while
7 * preserving certain parity constraints.
8 *
9 * @param s - The input binary string.
10 * @param k - The operation parameter controlling how counts can change.
11 * @returns The minimum number of operations, or -1 if unreachable.
12 */
13function minOperations(s: string, k: number): number {
14    // Length of the input string.
15    const length: number = s.length;
16
17    // Two AVL trees partitioned by parity (index 0 -> even, 1 -> odd).
18    // Each tree holds all not-yet-visited zero-counts of that parity.
19    const trees: [AvlTree<number>, AvlTree<number>] = [
20        new AvlTree<number>(),
21        new AvlTree<number>(),
22    ];
23
24    // Populate the trees with all possible counts from 0 to length,
25    // placing each value into the tree matching its parity.
26    for (let i = 0; i <= length; i++) {
27        trees[i % 2].insert(i);
28    }
29
30    // Count the number of '0' characters in the string (the start state).
31    let zeroCount: number = 0;
32    for (const ch of s) {
33        if (ch === '0') {
34            zeroCount++;
35        }
36    }
37
38    // Mark the starting count as visited by removing it from its tree.
39    trees[zeroCount % 2].remove(zeroCount);
40
41    // BFS queue initialized with the starting zero-count.
42    let queue: number[] = [zeroCount];
43
44    // The current BFS depth, equal to the number of operations performed.
45    let operations: number = 0;
46
47    // Perform a breadth-first search over reachable zero-counts.
48    while (queue.length > 0) {
49        // Holds the next BFS level's counts.
50        const nextQueue: number[] = [];
51
52        for (const current of queue) {
53            // Reaching a zero-count of 0 means the goal is achieved.
54            if (current === 0) {
55                return operations;
56            }
57
58            // Lower bound of the reachable count range after one operation.
59            const lower: number = current + k - 2 * Math.min(current, k);
60
61            // Upper bound of the reachable count range after one operation.
62            const upper: number =
63                current + k - 2 * Math.max(k - length + current, 0);
64
65            // Reachable counts share the parity of 'lower', so select
66            // the matching tree.
67            const tree: AvlTree<number> = trees[lower % 2];
68
69            // Find the first unvisited value >= lower, then iterate
70            // through all values within [lower, upper], visiting and
71            // removing each one.
72            let node = tree.upperBound(lower, true);
73            while (node && node.getValue() <= upper) {
74                const value: number = node.getValue();
75                nextQueue.push(value);
76                tree.remove(value);
77                // Find the next unvisited value strictly greater than 'lower';
78                // removed values are skipped automatically.
79                node = tree.upperBound(lower, false);
80            }
81        }
82
83        // Advance to the next BFS level.
84        queue = nextQueue;
85        operations++;
86    }
87
88    // No sequence of operations reaches a zero-count of 0.
89    return -1;
90}
91