problemmediumalgorithmsleetcode-2712leetcode 2712leetcode2712

Minimum Cost to Make All Characters Equal

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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 theminimum cost to make all characters of the string equal.

Invert a character means if its value is '0' it becomes '1' and vice-versa.

Examples

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^5
  • s[i] is either '0' or '1'

Solution

Method 1 – Greedy Two-Pass

Intuition

To make all characters equal, we can use either prefix or suffix invert operations. The optimal strategy is to find the minimum cost to make all characters '0' or all '1' by considering the cost of flipping at each index from left to right and right to left.

Approach

  1. For both target characters ('0' and '1'), do:
    • Traverse from left to right, keeping track of the cost to flip all to target using prefix operations.
    • Traverse from right to left, keeping track of the cost to flip all to target using suffix operations.
    • At each index, calculate the cost if we flip at that index and then flip the rest using the other operation.
  2. Return the minimum cost among all possibilities.

Code

C++
class Solution {
public:
    long long minimumCost(string s) {
        int n = s.size();
        long long ans = LLONG_MAX;
        for (char tgt : {'0', '1'}) {
            long long cost = 0;
            for (int i = 0; i < n; ++i) {
                if (s[i] != tgt) cost += i + 1;
            }
            ans = min(ans, cost);
            cost = 0;
            for (int i = n-1; i >= 0; --i) {
                if (s[i] != tgt) cost += n - i;
            }
            ans = min(ans, cost);
        }
        return ans;
    }
};
Go
func minimumCost(s string) int64 {
    n := len(s)
    ans := int64(1<<62)
    for _, tgt := range []byte{'0', '1'} {
        cost := int64(0)
        for i := 0; i < n; i++ {
            if s[i] != tgt { cost += int64(i+1) }
        }
        if cost < ans { ans = cost }
        cost = 0
        for i := n-1; i >= 0; i-- {
            if s[i] != tgt { cost += int64(n-i) }
        }
        if cost < ans { ans = cost }
    }
    return ans
}
Java
class Solution {
    public long minimumCost(String s) {
        int n = s.length();
        long ans = Long.MAX_VALUE;
        for (char tgt : new char[]{'0', '1'}) {
            long cost = 0;
            for (int i = 0; i < n; ++i) {
                if (s.charAt(i) != tgt) cost += i + 1;
            }
            ans = Math.min(ans, cost);
            cost = 0;
            for (int i = n-1; i >= 0; --i) {
                if (s.charAt(i) != tgt) cost += n - i;
            }
            ans = Math.min(ans, cost);
        }
        return ans;
    }
}
Kotlin
class Solution {
    fun minimumCost(s: String): Long {
        val n = s.length
        var ans = Long.MAX_VALUE
        for (tgt in listOf('0', '1')) {
            var cost = 0L
            for (i in 0 until n) {
                if (s[i] != tgt) cost += (i+1).toLong()
            }
            ans = minOf(ans, cost)
            cost = 0L
            for (i in n-1 downTo 0) {
                if (s[i] != tgt) cost += (n-i).toLong()
            }
            ans = minOf(ans, cost)
        }
        return ans
    }
}
Python
class Solution:
    def minimumCost(self, s: str) -> int:
        n = len(s)
        ans = float('inf')
        for tgt in '01':
            cost = sum(i+1 for i, c in enumerate(s) if c != tgt)
            ans = min(ans, cost)
            cost = sum(n-i for i, c in enumerate(s) if c != tgt)
            ans = min(ans, cost)
        return ans
Rust
impl Solution {
    pub fn minimum_cost(s: String) -> i64 {
        let n = s.len();
        let s = s.as_bytes();
        let mut ans = i64::MAX;
        for &tgt in &[b'0', b'1'] {
            let mut cost = 0;
            for i in 0..n {
                if s[i] != tgt { cost += (i+1) as i64; }
            }
            ans = ans.min(cost);
            cost = 0;
            for i in (0..n).rev() {
                if s[i] != tgt { cost += (n-i) as i64; }
            }
            ans = ans.min(cost);
        }
        ans
    }
}
TypeScript
class Solution {
    minimumCost(s: string): number {
        const n = s.length;
        let ans = Number.MAX_SAFE_INTEGER;
        for (const tgt of ['0', '1']) {
            let cost = 0;
            for (let i = 0; i < n; ++i) {
                if (s[i] !== tgt) cost += i+1;
            }
            ans = Math.min(ans, cost);
            cost = 0;
            for (let i = n-1; i >= 0; --i) {
                if (s[i] !== tgt) cost += n-i;
            }
            ans = Math.min(ans, cost);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the string, as we scan the string twice for each target.
  • 🧺 Space complexity: O(1).

Comments