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:
'0' in s.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:
[0, 1, 3]. s changes from "0101" to "1000".[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 <= 105s[i] is either '0' or '1'.1 <= k <= s.lengthProblem Overview: You are given a binary string and must compute the minimum number of operations required to transform it so all positions satisfy the equality condition defined in the problem. Each operation modifies positions in the string, and the challenge is finding the smallest sequence of transformations that leads to a valid equalized state.
Approach 1: Brute Force State Exploration (Exponential Time, O(2^n) time, O(2^n) space)
The most direct strategy treats every possible binary configuration as a state and explores transformations until an equalized string appears. A breadth-first search can generate neighboring states by applying every valid operation. Because the number of binary strings grows exponentially, this approach quickly becomes infeasible for large inputs. It is mainly useful for reasoning about correctness and validating small examples.
Approach 2: Component Grouping with Union Find (O(n α(n)) time, O(n) space)
Many constraints in binary string transformation problems effectively tie multiple indices together. If operations force certain positions to always change together, those indices can be merged into the same component using Union Find. After grouping indices, count how many 0s and 1s appear inside each component and compute the minimum flips required to make the component consistent. This dramatically reduces the state space because decisions are made per component instead of per index.
Approach 3: BFS with Ordered Set (O(n log n) time, O(n) space)
The optimized approach models the problem as a shortest-path search over indices that still violate the equality condition. Use Breadth-First Search to process positions whose value mismatches the required target. An ordered set keeps remaining unresolved indices sorted so you can quickly locate the next reachable positions affected by an operation. Each BFS expansion applies an operation, removes resolved indices from the set, and pushes newly affected positions into the queue. Because every index is inserted and removed at most once and ordered set operations cost O(log n), the total complexity becomes O(n log n).
Recommended for interviews: Interviewers expect the BFS + ordered set formulation. Brute force shows you understand the state-space model, while the optimized solution demonstrates the ability to prune transitions and manage active indices efficiently. The key insight is representing unresolved positions as a searchable structure and expanding them with BFS to guarantee the minimum number of operations.
We denote the length of string s as n, and the current number of '0's in the string as 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 cur + k - 2x.
The value of x needs to satisfy the following conditions:
min(cur, k) '0's can be taken, because we cannot flip more than cur '0's, so 0 leq x leq min(cur, k).n - cur '1's can be taken, because we cannot flip more than n - cur '1's, so k - x leq n - cur, i.e., x geq k - n + cur.Therefore, the range of x is [max(k - n + cur, 0), min(cur, k)], and the range of the number of '0's in the string after flipping is [cur + k - 2 cdot min(cur, k), cur + k - 2 cdot max(k - n + 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 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force State Exploration | O(2^n) | O(2^n) | Only for reasoning about small inputs or verifying correctness |
| Union Find Component Grouping | O(n α(n)) | O(n) | When operations link indices into forced groups |
| BFS + Ordered Set | O(n log n) | O(n) | General optimal solution for large strings with dynamic index updates |
Minimum Operations to Equalize Binary String | Brute Force | Optimal | Intuition | Leetcode 3666 • codestorywithMIK • 11,401 views views
Watch 9 more video solutions →Practice Minimum Operations to Equalize Binary String with our built-in code editor and test cases.
Practice on FleetCode