You are given a 0-indexed binary string s of length n on which you can apply two types of operations:
i and invert all characters from index 0 to index i (both inclusive), with a cost of i + 1i and invert all characters from index i to index n - 1 (both inclusive), with a cost of n - iReturn the minimum cost to make all characters of the string equal.
Invert a character means if its value is '0' it becomes '1' and vice-versa.
Example 1:
Input: s = "0011" Output: 2 Explanation: Apply the second operation withi = 2to obtains = "0000" for a cost of 2. It can be shown that 2 is the minimum cost to make all characters equal.
Example 2:
Input: s = "010101" Output: 9 Explanation: Apply the first operation with i = 2 to obtain s = "101101" for a cost of 3. Apply the first operation with i = 1 to obtain s = "011101" for a cost of 2. Apply the first operation with i = 0 to obtain s = "111101" for a cost of 1. Apply the second operation with i = 4 to obtain s = "111110" for a cost of 2. Apply the second operation with i = 5 to obtain s = "111111" for a cost of 1. The total cost to make all characters equal is 9. It can be shown that 9 is the minimum cost to make all characters equal.
Constraints:
1 <= s.length == n <= 105s[i] is either '0' or '1'Problem Overview: You are given a binary string s. In one operation you can flip either a prefix or a suffix of the string, and the cost equals the length of the flipped segment. The goal is to make all characters in the string equal with the minimum total cost.
Approach 1: Prefix and Suffix Flips (Greedy) (Time: O(n), Space: O(1))
The key observation: cost only matters when the character changes between adjacent positions. When you encounter a boundary where s[i] != s[i-1], you must perform a flip to make that region consistent with the rest. You have two options: flip the prefix ending at i-1 with cost i, or flip the suffix starting at i with cost n-i. The optimal choice is simply min(i, n-i). Iterate through the string once, detect every transition, and accumulate this minimum cost. This works because each boundary can be resolved independently, and choosing the cheaper side always leads to the minimal global cost. The algorithm uses simple iteration over the string and a greedy decision at each change point, making it both efficient and easy to implement.
Approach 2: Counting Zero Blocks and One Blocks (Greedy / DP Insight) (Time: O(n), Space: O(1))
Another way to reason about the problem is by grouping consecutive characters into blocks. Each block of 0s or 1s represents a segment that may need merging with neighboring blocks. When the character changes, you effectively decide whether to flip everything before the boundary or everything after it. Instead of thinking about individual operations, treat each boundary as a cost decision and sum the cheaper direction. This perspective highlights the relationship between block transitions and minimal flip operations. The method still runs in linear time because you scan the string once and count transitions between blocks. The logic connects closely to problems involving greedy decisions and boundary-based dynamic programming reasoning.
Recommended for interviews: The greedy boundary approach (Prefix and Suffix Flips) is the solution most interviewers expect. It shows you recognized that only transition points matter and that each can be solved independently using min(i, n-i). Explaining the block interpretation demonstrates deeper reasoning, but implementing the greedy scan proves strong algorithmic intuition and leads directly to the optimal O(n) solution.
The idea is to make use of prefix and suffix operations for the string. We calculate the cost to make the entire string '0s' or '1s' by considering two symmetrical operations (flipping section from the start or end). By evaluating cost at each possible split, we can determine the minimal flipping cost.
This solution iterates through the string, calculating the cost of flipping all characters to '0's and all to '1's separately. It returns the lower cost. This approach runs in O(n) time.
Time Complexity: O(n)
Space Complexity: O(1) (no additional data structures are used)
This approach revolves around counting the number of contiguous blocks of '0's and '1's. Each switch from '0' to '1' or vice-versa may require handling individually. Subsequently, compute potential costs based on turning each entire block into one containing only one type of character.
This implementation considers the start and end transformations separately, tallying potential conversion costs whenever a new contiguous block starts or ends.
Time Complexity: O(n)
Space Complexity: O(1)
According to the problem description, if s[i] neq s[i - 1], an operation must be performed; otherwise, it's impossible to make all characters equal.
We can either choose to reverse all characters from s[0..i-1], with a cost of i, or reverse all characters from s[i..n-1], with a cost of n - i. We take the minimum of the two.
By iterating through the string s and summing up the costs of all characters that need to be reversed, we can obtain the minimum cost.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Prefix and Suffix Flips | Time Complexity: O(n) |
| Counting Zero Blocks and One Blocks | Time Complexity: O(n) |
| Greedy Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Flips (Greedy) | O(n) | O(1) | Best general solution. Single pass over the string with minimal memory. |
| Counting Zero and One Blocks | O(n) | O(1) | Useful for understanding the problem through block transitions and greedy cost choices. |
Leetcode Weekly contest 347 - Medium - Minimum Cost to Make All Characters Equal • Prakhar Agrawal • 2,022 views views
Watch 9 more video solutions →Practice Minimum Cost to Make All Characters Equal with our built-in code editor and test cases.
Practice on FleetCode