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⁵
s[i] is either '0' or '1'.
1 <= k <= s.length

Solutions

Solution 1

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;
    }
}

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;
    }
};

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

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
}

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;
}

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
    }
}

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;
    }
}

3666 - Minimum Operations to Equalize Binary String

3666. Minimum Operations to Equalize Binary String

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3666. Minimum Operations to Equalize Binary String

Description

Solutions

Solution 1

All Problems

All Solutions