Skip to content

3666. Minimum Operations to Equalize Binary String

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' in s.
  • 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]. s changes from "0101" to "1000".
  • Operation 2: Flip indices [1, 2, 3]. s changes 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 <= 10​​​​​​​5
  • s[i] is either '0' or '1'.
  • 1 <= k <= s.length

Solutions

Solution 1: BFS + Ordered Set

We denote the length of string \(s\) as \(n\), and the current number of '0's in the string as \(\textit{cur}\). In each operation, we select \(k\) indices to flip, where \(x\) indices flip from '0' to '1', and \(k-x\) indices flip from '1' to '0'. Then the number of '0's in the string after flipping is \(\textit{cur} + k - 2x\).

The value of \(x\) needs to satisfy the following conditions:

  1. At most \(\min(\textit{cur}, k)\) '0's can be taken, because we cannot flip more than \(\textit{cur}\) '0's, so \(0 \leq x \leq \min(\textit{cur}, k)\).
  2. At most \(n - \textit{cur}\) '1's can be taken, because we cannot flip more than \(n - \textit{cur}\) '1's, so \(k - x \leq n - \textit{cur}\), i.e., \(x \geq k - n + \textit{cur}\).

Therefore, the range of \(x\) is \([\max(k - n + \textit{cur}, 0), \min(\textit{cur}, k)]\), and the range of the number of '0's in the string after flipping is \([\textit{cur} + k - 2 \cdot \min(\textit{cur}, k), \textit{cur} + k - 2 \cdot \max(k - n + \textit{cur}, 0)]\).

We notice that the parity of the number of '0's in the string after flipping is the same as the parity of the number of '0's in the string before flipping. Therefore, we can use two ordered sets to store states where the number of '0's is even and odd, respectively.

We use BFS to search the state transition graph, where the initial state is the number of '0's in the string, and the target state is 0. Each time we dequeue a state \(\textit{cur}\), we calculate the range \([l, r]\) of the number of '0's in the string after flipping, find all states in the range \([l, r]\) in the ordered set, add them to the queue, and remove them from the ordered set.

If we visit state 0 during the BFS process, we return the current number of operations; if state 0 is not visited after BFS ends, we return -1.

The time complexity is \(O(n \log n)\), and the space complexity is \(O(n)\), where \(O(n)\) is the number of states that may be visited during the BFS process, and \(O(\log n)\) is the time complexity of inserting and deleting elements in the ordered set.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minOperations(self, s: str, k: int) -> int:
        n = len(s)
        ts = [SortedSet() for _ in range(2)]
        for i in range(n + 1):
            ts[i % 2].add(i)
        cnt0 = s.count('0')
        ts[cnt0 % 2].remove(cnt0)
        q = deque([cnt0])
        ans = 0
        while q:
            for _ in range(len(q)):
                cur = q.popleft()
                if cur == 0:
                    return ans
                l = cur + k - 2 * min(cur, k)
                r = cur + k - 2 * max(k - n + cur, 0)
                t = ts[l % 2]
                j = t.bisect_left(l)
                while j < len(t) and t[j] <= r:
                    q.append(t[j])
                    t.remove(t[j])
            ans += 1
        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
48
49
class Solution {
    public int minOperations(String s, int k) {
        int n = s.length();

        TreeSet<Integer>[] ts = new TreeSet[2];
        Arrays.setAll(ts, i -> new TreeSet<>());

        for (int i = 0; i <= n; i++) {
            ts[i % 2].add(i);
        }

        int cnt0 = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                cnt0++;
            }
        }

        ts[cnt0 % 2].remove(cnt0);

        Deque<Integer> q = new ArrayDeque<>();
        q.offer(cnt0);

        int ans = 0;
        while (!q.isEmpty()) {
            for (int size = q.size(); size > 0; --size) {
                int cur = q.poll();
                if (cur == 0) {
                    return ans;
                }

                int l = cur + k - 2 * Math.min(cur, k);
                int r = cur + k - 2 * Math.max(k - n + cur, 0);

                TreeSet<Integer> t = ts[l % 2];

                Integer next = t.ceiling(l);
                while (next != null && next <= r) {
                    q.offer(next);
                    t.remove(next);
                    next = t.ceiling(l);
                }
            }
            ans++;
        }

        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
class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.size();

        set<int> ts[2];
        for (int i = 0; i <= n; i++) {
            ts[i % 2].insert(i);
        }

        int cnt0 = count(s.begin(), s.end(), '0');
        ts[cnt0 % 2].erase(cnt0);

        queue<int> q;
        q.push(cnt0);

        int ans = 0;

        while (!q.empty()) {
            for (int size = q.size(); size > 0; --size) {
                int cur = q.front();
                q.pop();
                if (cur == 0) {
                    return ans;
                }

                int l = cur + k - 2 * min(cur, k);
                int r = cur + k - 2 * max(k - n + cur, 0);

                auto& t = ts[l % 2];
                auto it = t.lower_bound(l);

                while (it != t.end() && *it <= r) {
                    q.push(*it);
                    it = t.erase(it);
                }
            }
            ans++;
        }

        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
func minOperations(s string, k int) int {
    n := len(s)

    ts := [2]*redblacktree.Tree{
        redblacktree.NewWithIntComparator(),
        redblacktree.NewWithIntComparator(),
    }

    for i := 0; i <= n; i++ {
        ts[i%2].Put(i, struct{}{})
    }

    cnt0 := strings.Count(s, "0")
    ts[cnt0%2].Remove(cnt0)

    q := []int{cnt0}
    ans := 0

    for len(q) > 0 {
        nq := []int{}

        for _, cur := range q {
            if cur == 0 {
                return ans
            }

            l := cur + k - 2*min(cur, k)
            r := cur + k - 2*max(k-n+cur, 0)
            t := ts[l%2]

            node, found := t.Ceiling(l)
            for found && node.Key.(int) <= r {
                val := node.Key.(int)
                nq = append(nq, val)
                t.Remove(val)
                node, found = t.Ceiling(l)
            }
        }

        q = nq
        ans++
    }

    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
48
import { AvlTree } from '@datastructures-js/binary-search-tree';

function minOperations(s: string, k: number): number {
    const n: number = s.length;

    const ts = [new AvlTree<number>(), new AvlTree<number>()];

    for (let i = 0; i <= n; i++) {
        ts[i % 2].insert(i);
    }

    let cnt0 = 0;
    for (const c of s) {
        if (c === '0') cnt0++;
    }

    ts[cnt0 % 2].remove(cnt0);

    let q: number[] = [cnt0];
    let ans = 0;

    while (q.length > 0) {
        const nq: number[] = [];

        for (const cur of q) {
            if (cur === 0) {
                return ans;
            }

            const l = cur + k - 2 * Math.min(cur, k);
            const r = cur + k - 2 * Math.max(k - n + cur, 0);

            const t = ts[l % 2];
            let node = t.upperBound(l, true);
            while (node && node.getValue() <= r) {
                const val = node.getValue();
                nq.push(val);
                t.remove(val);
                node = t.upperBound(l, false);
            }
        }

        q = nq;
        ans++;
    }

    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
48
49
use std::collections::{BTreeSet, VecDeque};

impl Solution {
    pub fn min_operations(s: String, k: i32) -> i32 {
        let n: i32 = s.len() as i32;
        let k: i32 = k;

        let mut ts: [BTreeSet<i32>; 2] = [BTreeSet::new(), BTreeSet::new()];
        for i in 0..=n {
            ts[(i % 2) as usize].insert(i);
        }

        let cnt0: i32 = s.bytes().filter(|&c| c == b'0').count() as i32;
        ts[(cnt0 % 2) as usize].remove(&cnt0);

        let mut q: VecDeque<i32> = VecDeque::new();
        q.push_back(cnt0);

        let mut ans: i32 = 0;

        while !q.is_empty() {
            let size = q.len();
            for _ in 0..size {
                let cur = q.pop_front().unwrap();
                if cur == 0 {
                    return ans;
                }

                let l = cur + k - 2 * cur.min(k);
                let r = cur + k - 2 * (k - n + cur).max(0);

                let parity = (l % 2) as usize;

                let vals: Vec<i32> = ts[parity]
                    .range(l..=r)
                    .cloned()
                    .collect();

                for v in vals {
                    q.push_back(v);
                    ts[parity].remove(&v);
                }
            }
            ans += 1;
        }

        -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
48
49
50
51
52
53
54
55
public class Solution {
    public int MinOperations(string s, int k) {
        int n = s.Length;

        var ts = new SortedSet<int>[2];
        ts[0] = new SortedSet<int>();
        ts[1] = new SortedSet<int>();

        for (int i = 0; i <= n; i++) {
            ts[i % 2].Add(i);
        }

        int cnt0 = 0;
        foreach (char c in s) {
            if (c == '0') {
                cnt0++;
            }
        }

        ts[cnt0 % 2].Remove(cnt0);

        var q = new Queue<int>();
        q.Enqueue(cnt0);

        int ans = 0;

        while (q.Count > 0) {
            int size = q.Count;
            for (int i = 0; i < size; i++) {
                int cur = q.Dequeue();
                if (cur == 0) {
                    return ans;
                }

                int l = cur + k - 2 * Math.Min(cur, k);
                int r = cur + k - 2 * Math.Max(k - n + cur, 0);

                var t = ts[l % 2];

                var toRemove = new List<int>();
                foreach (int next in t.GetViewBetween(l, r)) {
                    q.Enqueue(next);
                    toRemove.Add(next);
                }

                foreach (int next in toRemove) {
                    t.Remove(next);
                }
            }
            ans++;
        }

        return -1;
    }
}

Comments