2712 Minimum Cost to Make All Characters Equal Solution

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.

The problem

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.

Python

def min_cost_to_make_equal(s):
    n = len(s)
    cost_one = 0
    cost_zero = 0
    for i, char in enumerate(s):
        if char == '1':
            cost_zero += i + 1
        else:
            cost_one += i + 1
    return min(cost_one, cost_zero)

s = "010101"
print(min_cost_to_make_equal(s))

Java

public class Main {
    public static int minCostToMakeEqual(String s) {
        int n = s.length();
        int costOne = 0, costZero = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '1') costZero += i + 1;
            if (s.charAt(i) == '0') costOne += i + 1;
        }
        return Math.min(costOne, costZero);
    }

    public static void main(String[] args) {
        String s = "010101";
        System.out.println(minCostToMakeEqual(s));
    }
}

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int minCostToMakeEqual(string s) {
    int n = s.size();
    int costOne = 0, costZero = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') costZero += i + 1;
        if (s[i] == '0') costOne += i + 1;
    }
    return min(costOne, costZero);
}

int main() {
    string s = "010101";
    cout << minCostToMakeEqual(s) << endl;
    return 0;
}

JavaScript

function minCostToMakeEqual(s) {
    const n = s.length;
    let costOne = 0, costZero = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] === '1') costZero += i + 1;
        if (s[i] === '0') costOne += i + 1;
    }
    return Math.min(costOne, costZero);
}

const s = "010101";
console.log(minCostToMakeEqual(s));

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minCostToMakeEqual(char *s) {
    int n = strlen(s);
    int costToOnes = 0, costToZeros = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') costToZeros += i + 1;
        if (s[i] == '0') costToOnes += i + 1;
    }
    int ans = costToOnes < costToZeros ? costToOnes : costToZeros;
    return ans;
}

int main() {
    char s[] = "010101";
    printf("%d\n", minCostToMakeEqual(s));
    return 0;
}

using System;

public class Program {
    public static int MinCostToMakeEqual(string s) {
        int n = s.Length;
        int costOne = 0, costZero = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') costZero += i + 1;
            if (s[i] == '0') costOne += i + 1;
        }
        return Math.Min(costOne, costZero);
    }
    
    public static void Main() {
        string s = "010101";
        Console.WriteLine(MinCostToMakeEqual(s));
    }
}

The Python code is straightforward: it loops through the string, counting each type of change cost, and selects the minimal option.

Complexity

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

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.

Python

def min_cost_to_make_equal(s):
    n = len(s)
    cost = float('inf')
    prefix_count = s.count('1')
    suffix_count = 0
    for i in range(n + 1):
        if i > 0 and s[i - 1] == '0':
            prefix_count += 1
        if i < n and s[i] == '1':
            suffix_count += 1
        cost = min(cost, prefix_count + suffix_count)
    return cost

s = "010101"
print(min_cost_to_make_equal(s))

Java

public class Main {
    public static int minCostToMakeEqual(String s) {
        int n = s.length();
        int cost = Integer.MAX_VALUE, prefixCount = 0, suffixCount = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') prefixCount++;
        }
        for (int i = 0; i <= n; i++) {
            if (i > 0 && s.charAt(i - 1) == '0') prefixCount++;
            if (i < n && s.charAt(i) == '1') suffixCount++;
            cost = Math.min(cost, prefixCount + suffixCount);
        }
        return cost;
    }
    
    public static void main(String[] args) {
        String s = "010101";
        System.out.println(minCostToMakeEqual(s));
    }
}

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int minCostToMakeEqual(string s) {
    int n = s.size();
    int cost = INT_MAX, prefixCount = 0, suffixCount = 0;
    for (char c : s) {
        if (c == '1') prefixCount++;
    }
    for (int i = 0; i <= n; i++) {
        if (i > 0 && s[i - 1] == '0') prefixCount++;
        if (i < n && s[i] == '1') suffixCount++;
        cost = min(cost, prefixCount + suffixCount);
    }
    return cost;
}

int main() {
    string s = "010101";
    cout << minCostToMakeEqual(s) << endl;
    return 0;
}

JavaScript

function minCostToMakeEqual(s) {
    const n = s.length;
    let cost = Infinity, prefixCount = 0, suffixCount = 0;
    prefixCount = [...s].filter(char => char === '1').length;
    for (let i = 0; i <= n; i++) {
        if (i > 0 && s[i - 1] === '0') prefixCount++;
        if (i < n && s[i] === '1') suffixCount++;
        cost = Math.min(cost, prefixCount + suffixCount);
    }
    return cost;
}

const s = "010101";
console.log(minCostToMakeEqual(s));

#include <stdio.h>
#include <string.h>
#include <limits.h>

int minCostToMakeEqual(char *s) {
    int n = strlen(s);
    int cost = INT_MAX, prefixCount = 0, suffixCount = 0;
    int flipCount = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') prefixCount++;
    }
    for (int i = 0; i <= n; i++) {
        if (i > 0 && s[i - 1] == '0') prefixCount++;
        if (i < n && s[i] == '1') suffixCount++;
        cost = cost < (prefixCount + suffixCount) ? cost : (prefixCount + suffixCount);
    }
    return cost;
}

int main() {
    char s[] = "010101";
    printf("%d\n", minCostToMakeEqual(s));
    return 0;
}

using System;

public class Program {
    public static int MinCostToMakeEqual(string s) {
        int n = s.Length;
        int cost = Int32.MaxValue, prefixCount = 0, suffixCount = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') prefixCount++;
        }
        for (int i = 0; i <= n; i++) {
            if (i > 0 && s[i - 1] == '0') prefixCount++;
            if (i < n && s[i] == '1') suffixCount++;
            cost = Math.Min(cost, prefixCount + suffixCount);
        }
        return cost;
    }
    
    public static void Main() {
        string s = "010101";
        Console.WriteLine(MinCostToMakeEqual(s));
    }
}

The solution sweeps through string characters, toggling counter values for alternate character runs, ultimately minimizing transformations.

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

TypeScript

function minimumCost(s: string): number {
    let ans = 0;
    const n = s.length;
    for (let i = 1; i < n; ++i) {
        if (s[i] !== s[i - 1]) {
            ans += Math.min(i, n - i);
        }
    }
    return ans;
}

func minimumCost(s string) (ans int64) {
	n := len(s)
	for i := 1; i < n; i++ {
		if s[i] != s[i-1] {
			ans += int64(min(i, n-i))
		}
	}
	return
}

Rust

impl Solution {
    pub fn minimum_cost(s: String) -> i64 {
        let mut ans = 0;
        let n = s.len();
        let s = s.as_bytes();
        for i in 1..n {
            if s[i] != s[i - 1] {
                ans += i.min(n - i);
            }
        }
        ans as i64
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prefix and Suffix Flips	Time Complexity: O(n) Space Complexity: O(1)
Counting Zero Blocks and One Blocks	Time Complexity: O(n) Space Complexity: O(1)
Greedy Algorithm	–

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.

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.

Minimum Cost to Make All Characters Equal solution and explanation

The problem

Approach overview

Approach 1: Prefix and Suffix Flips

Approach 2: Counting Zero Blocks and One Blocks

Approach 3: Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Cost to Make All Characters Equal solution and explanation

The problem

Approach overview

Approach 1: Prefix and Suffix Flips

Approach 2: Counting Zero Blocks and One Blocks

Approach 3: Greedy Algorithm

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems