Minimum Cost to Make All Characters Equal — Medium Problem & Solution

Problem statement

You are given a binary string s of length n. Two kinds of operation are available, and you may use them any number of times:

• Choose an index i and invert every character from index 0 to i (inclusive). This costs i + 1.
• Choose an index i and invert every character from index i to n - 1 (inclusive). This costs n - i.

Inverting turns '0' into '1' and '1' into '0'. Return the minimum total cost to make all characters of the string equal.

The original allows n up to 10^5; here n <= 5 · 10^4 so the cost fits in a 32-bit integer.

Example 1

Input: s = "0110"
Output: 2
Explanation: Invert the suffix from index 3 (cost 1) and the prefix up to index 0 (cost 1): `1111`.

Example 2

Input: s = "10101"
Output: 6

Example 3

Input: s = "1"
Output: 0

Constraints

• 1 <= s.length == n <= 5 * 10^4
• s[i] is '0' or '1'

How to solve Minimum Cost to Make All Characters Equal

Only the boundaries between different neighbours matter. A prefix inversion ending at i - 1 or a suffix inversion starting at i toggles exactly the boundary between positions i - 1 and i, so each boundary is paid for separately at min(i, n - i).

Approach

1. Set ans = 0.
2. For each i from 1 to n - 1 with s[i] != s[i - 1], add min(i, n - i).
3. Return ans.

Why it works

Inverting a prefix [0, i-1] (cost i) or a suffix [i, n-1] (cost n - i) changes whether position i - 1 equals position i, and no other adjacent pair. The string is uniform exactly when no boundary remains, so every boundary needs at least one operation at its own position, costing at least min(i, n - i); doing exactly that cheapest one for each boundary achieves the bound.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The prefix ending at index i - 1 costs i, not i - 1 — mind the off-by-one between index and cost.
• It does not matter whether the final string is all zeros or all ones; the boundary count decides.
• Under the original n <= 10^5 the total needs 64 bits.

Reference solution

Python

def minimumCost(s: str) -> int:
    n = len(s)
    return sum(min(i, n - i) for i in range(1, n) if s[i] != s[i - 1])

JavaScript

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

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Ambiguous Coordinates Medium
• Generate Binary Strings Without Adjacent Zeros Medium
• Splitting a String Into Descending Consecutive Values Medium
• Letter Case Permutation Medium
• Lexicographically Smallest Equivalent String Medium
• Extra Characters in a String Medium