LeetCode 3666 | Minimum Operations to Equalize Binary String | BFS + Math | Java | Hard

Описание: LeetCode 3666 – Minimum Operations to Equalize Binary String (Java)

Today's LeetCode Daily

You are given a binary string s and an integer k.

In one operation:
Choose exactly k different indices
and flip each bit.

Goal:
Make all characters equal to 1
using minimum operations.

Core Insight:

Instead of tracking the full string,
we only track the number of zeros.

Why?
Because each operation changes
the zero count deterministically.

If current zero count is curr,
after flipping k bits,
new zero count depends on:
how many zeros we flipped
how many ones we flipped

This creates a range of reachable
zero counts.

Approach Used:

✔ Count initial zeros
✔ If zero count is 0 → return 0

✔ Use BFS on zero count states
✔ steps array tracks minimum operations
✔ Maintain two TreeSets:
one for even counts
one for odd counts

Parity matters because
zero count parity changes
based on k.

For each state:
Compute minReach and maxReach
which defines reachable zero counts.

Use TreeSet ceiling to efficiently
visit valid next states.

Stop when zero count becomes 0.

Key Idea:
Convert problem into graph traversal
over zero count states.
Use BFS to find shortest path.

Time Complexity:
Approximately O(n log n)

Space Complexity:
O(n)

Problem Link:
https://leetcode.com/problems/minimum...

Java Solution (GitHub):
https://github.com/Amandf/LeetCode-So...

More daily Java solutions.
Clean code. No mic. Pure logic.

#leetcode #leetcodedailychallenge #java #bfs #graphtraversal #hardproblem #dsa #codinginterview #programming