Skip to main content
Talentd

Minimum Operations to Equalize Binary String - Solution & Explanation

HardMathStringBreadth-First SearchUnion Find20 min readAsked at: Amazon, Microsoft, Infosys +1
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Solution

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:

  1. At most 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).
  2. At most 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.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force State ExplorationO(2^n)O(2^n)Only for reasoning about small inputs or verifying correctness
Union Find Component GroupingO(n Ī±(n))O(n)When operations link indices into forced groups
BFS + Ordered SetO(n log n)O(n)General optimal solution for large strings with dynamic index updates

Video Solution

Minimum Operations to Equalize Binary String | Brute Force | Optimal | Intuition | Leetcode 3666 ā€¢ codestorywithMIK ā€¢ 12,212 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Minimum Operations to Equalize Binary String easy or hard?
Minimum Operations to Equalize Binary String is categorized as a Hard problem. It combines string processing with graph traversal and advanced data structures such as ordered sets or union find. The difficulty comes from modeling the operations efficiently and avoiding exponential state exploration.
Minimum Operations to Equalize Binary String Python/Java solution
Python implementations commonly use collections.deque for BFS and sorted containers or tree-like structures to simulate an ordered set. Java solutions typically rely on TreeSet for ordered index management along with a queue for BFS traversal. Both achieve O(n log n) time complexity.
How to solve Minimum Operations to Equalize Binary String in O(n)?
Pure O(n) solutions are difficult because efficient index lookup and removal are required during state expansion. Most optimal implementations rely on ordered sets or balanced trees, leading to O(n log n) complexity. BFS ensures minimal operations while the ordered structure maintains the next unresolved indices efficiently.
What is the best approach for Minimum Operations to Equalize Binary String?
The most efficient approach uses Breadth-First Search combined with an ordered set to track unresolved indices. BFS guarantees the minimum number of operations, while the ordered set allows fast insertion, deletion, and neighbor lookup. This combination processes each index once and results in O(n log n) time complexity with O(n) space.
Is Minimum Operations to Equalize Binary String asked at Google/Amazon/Meta?
Hard string and graph-style transformation problems similar to this appear frequently in Google, Amazon, and Meta interview rounds. They test your ability to model a problem as a graph, apply BFS for shortest operations, and optimize index tracking with advanced data structures.
What data structure is used in Minimum Operations to Equalize Binary String?
The optimized solution typically uses a BFS queue plus an ordered set or balanced tree structure. The queue handles level-by-level exploration of operations, while the ordered set stores unresolved indices and supports fast range queries and deletions in O(log n).
What is the time complexity of Minimum Operations to Equalize Binary String?
The optimal solution runs in O(n log n) time using BFS with an ordered set. Each index is inserted and removed from the ordered structure at most once, and each such operation costs O(log n). The overall space complexity is O(n) for the queue and index tracking structures.

Ready to solve this problem?

Practice Minimum Operations to Equalize Binary String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer