Minimum Cost to Make All Characters Equal - Solution & Explanation

Q: Is Minimum Cost to Make All Characters Equal easy or hard?

The problem is rated Medium because the implementation is simple but the key insight is not immediately obvious. Recognizing that only character transitions matter and choosing min(i, n-i) at each boundary is the core trick.

Q: Minimum Cost to Make All Characters Equal Python/Java solution

In Python or Java, the implementation follows the same pattern: loop through the string, check if s[i] != s[i-1], and add min(i, n-i) to the result. Because the algorithm is linear and uses constant space, it performs efficiently even for large inputs.

Q: How to solve Minimum Cost to Make All Characters Equal in O(n)?

Iterate through the string from index 1 to n-1. Every time the current character differs from the previous one, add min(i, n-i) to the total cost. This greedy decision ensures you always choose the cheaper side to flip while resolving each transition.

Q: What is the best approach for Minimum Cost to Make All Characters Equal?

The optimal approach uses a greedy scan of the string. Whenever the character changes at index i (s[i] != s[i-1]), you choose the cheaper operation between flipping the prefix of length i or the suffix of length n-i. Adding min(i, n-i) for each transition gives the minimum cost. This runs in O(n) time and O(1) space.

Q: Is Minimum Cost to Make All Characters Equal asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving greedy decisions on string transitions. Variants of similar problems appear in interviews at large tech companies like Google, Amazon, and Meta where candidates must optimize operations on strings or arrays.

Q: What data structure is used in Minimum Cost to Make All Characters Equal?

The solution mainly uses simple string traversal and greedy logic. No complex data structures are required. The algorithm relies on iterating through the string and checking transitions between adjacent characters.

Q: What is the time complexity of Minimum Cost to Make All Characters Equal?

The optimal solution runs in O(n) time because the algorithm scans the string once and processes each adjacent pair exactly one time. Space complexity is O(1) since only a few variables are needed to track the running cost and index positions.

MediumString Dynamic Programming Greedy16 min readAsked at: Nutanix

Practice this problem

Problem Statement

You are given a 0-indexed binary string s of length n on which you can apply two types of operations:

Choose an index i and invert all characters from index 0 to index i (both inclusive), with a cost of i + 1
Choose an index i and invert all characters from index i to index n - 1 (both inclusive), with a cost of n - i

Return 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 with i = 2 to obtain s = "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 <= 10⁵
s[i] is either '0' or '1'

Approach Overview

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.

Approach 1: Prefix and Suffix Flips

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1) (no additional data structures are used)

Try this approach in the editor →

Approach 2: Counting Zero Blocks and One Blocks

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Greedy Algorithm

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

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Prefix and Suffix Flips	Time Complexity: O(n) Space Complexity: O(1) (no additional data structures are used)
Counting Zero Blocks and One Blocks	Time Complexity: O(n) Space Complexity: O(1)
Greedy Algorithm	—

Detailed Complexity Analysis

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.

Video Solution

Leetcode Weekly contest 347 - Medium - Minimum Cost to Make All Characters Equal • Prakhar Agrawal • 2,040 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Cost to Make All Characters Equal easy or hard?

The problem is rated Medium because the implementation is simple but the key insight is not immediately obvious. Recognizing that only character transitions matter and choosing min(i, n-i) at each boundary is the core trick.

Minimum Cost to Make All Characters Equal Python/Java solution

In Python or Java, the implementation follows the same pattern: loop through the string, check if s[i] != s[i-1], and add min(i, n-i) to the result. Because the algorithm is linear and uses constant space, it performs efficiently even for large inputs.

How to solve Minimum Cost to Make All Characters Equal in O(n)?

Iterate through the string from index 1 to n-1. Every time the current character differs from the previous one, add min(i, n-i) to the total cost. This greedy decision ensures you always choose the cheaper side to flip while resolving each transition.

What is the best approach for Minimum Cost to Make All Characters Equal?

The optimal approach uses a greedy scan of the string. Whenever the character changes at index i (s[i] != s[i-1]), you choose the cheaper operation between flipping the prefix of length i or the suffix of length n-i. Adding min(i, n-i) for each transition gives the minimum cost. This runs in O(n) time and O(1) space.

Is Minimum Cost to Make All Characters Equal asked at Google/Amazon/Meta?

This problem represents a common interview pattern involving greedy decisions on string transitions. Variants of similar problems appear in interviews at large tech companies like Google, Amazon, and Meta where candidates must optimize operations on strings or arrays.

What data structure is used in Minimum Cost to Make All Characters Equal?

The solution mainly uses simple string traversal and greedy logic. No complex data structures are required. The algorithm relies on iterating through the string and checking transitions between adjacent characters.

What is the time complexity of Minimum Cost to Make All Characters Equal?

The optimal solution runs in O(n) time because the algorithm scans the string once and processes each adjacent pair exactly one time. Space complexity is O(1) since only a few variables are needed to track the running cost and index positions.

Ready to solve this problem?

Practice Minimum Cost to Make All Characters Equal with our built-in code editor and test cases.

Practice on FleetCode

Flip String to Monotone Increasing

Problem Info

DifficultyMedium

Acceptance54.3%

Approaches3

Reading time16 min

Asked at

Nutanix

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Prefix and Suffix Flips

Code

Complexity

Approach 2: Counting Zero Blocks and One Blocks

Code

Complexity

Approach 3: Greedy Algorithm

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents