LeetCode 2712 - Minimum Cost to Make All Characters Equal

LeetCode Problem 2712

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem gives us a binary string s consisting only of characters '0' and '1'. Our goal is to make every character in the string equal, meaning the final string must become either all '0' characters or all '1' characters.

We are allowed to perform two types of operations:

1. Choose an index i and flip every character from the beginning of the string up to index i. This operation affects the prefix s[0...i] and costs i + 1.
2. Choose an index i and flip every character from index i to the end of the string. This operation affects the suffix s[i...n-1] and costs n - i.

Flipping means changing '0' to '1' and '1' to '0'.

The challenge is to determine the minimum total cost required to transform the string so that all characters are identical.

The constraint n <= 10^5 immediately tells us that expensive brute-force simulation approaches are not practical. Any algorithm worse than roughly linear or near-linear time will likely time out.

An important observation is that the string only matters at positions where adjacent characters differ. If two neighboring characters are already equal, there is no reason to perform an operation specifically between them. Every transition between '0' and '1' represents a boundary that eventually must be resolved.

Several edge cases are important:

• A string that is already uniform, such as "0000" or "111", should return 0.
• A string of length 1 is already valid, so the answer is always 0.
• Alternating strings like "010101" create many transitions and test whether the algorithm correctly accumulates costs.
• Very large strings require an efficient solution that avoids repeated flipping simulations.

Approaches

Brute Force Approach

A brute-force strategy would attempt to simulate different sequences of operations to transform the string into either all '0' or all '1'.

For every mismatch between neighboring characters, we could consider whether to fix it using a prefix flip or a suffix flip. Since each boundary introduces two possible choices, the number of operation combinations grows exponentially.

Another brute-force variation would use BFS or dynamic programming over string states. Each operation creates a new string configuration, and we would search for the minimum-cost path to a uniform string.

These methods are theoretically correct because they explore all possible valid transformations, but they are computationally infeasible. The number of possible states is enormous, especially when n can reach 100000.

Key Insight for the Optimal Solution

The crucial observation is that only transitions matter.

Suppose we examine two adjacent characters s[i-1] and s[i].

• If they are equal, nothing needs to be done between them.
• If they differ, eventually some operation must cross this boundary to make them equal.

To resolve a transition at position i, we have exactly two efficient choices:

• Flip the prefix ending at i-1, with cost i
• Flip the suffix starting at i, with cost n - i

We should always choose the cheaper of these two options.

Therefore, for every adjacent mismatch, we add:

min(i, n - i)

The remarkable property is that these choices are independent. Each transition contributes its own minimum unavoidable cost.

This leads to a simple linear scan solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores many possible operation sequences
Optimal	O(n)	O(1)	Adds minimum cost for every character transition

Algorithm Walkthrough

1. Initialize a variable total_cost to 0.

This variable will store the minimum total cost required to make the string uniform. 2. Iterate through the string from index 1 to n - 1.

At each position i, compare s[i] with s[i-1]. 3. Check whether a transition exists.

If s[i] == s[i-1], then these neighboring characters are already equal, so no action is needed.

If s[i] != s[i-1], then there is a boundary between different character groups that must eventually be fixed. 4. Compute the cheapest way to resolve the transition.

We have two options:

• Flip the prefix ending before index i, costing i
• Flip the suffix starting at index i, costing n - i

Add the smaller value to total_cost. 5. Continue scanning until the end of the string.

Every transition contributes independently to the final answer. 6. Return total_cost.

Why it works

Every adjacent mismatch represents a required boundary correction. No matter what sequence of operations we perform, each transition must be crossed at least once by some flip operation.

For a transition at index i, the cheapest possible operation affecting that boundary costs either i or n - i. Choosing the minimum guarantees the lowest contribution for that boundary.

Since boundaries are independent, summing these minimum costs over all transitions produces the global minimum cost.

Python Solution

class Solution:
    def minimumCost(self, s: str) -> int:
        n = len(s)
        total_cost = 0

        for i in range(1, n):
            if s[i] != s[i - 1]:
                total_cost += min(i, n - i)

        return total_cost

The implementation begins by storing the length of the string in n. We then initialize total_cost to accumulate the answer.

The loop starts from index 1 because we compare each character with its previous neighbor. Whenever two adjacent characters differ, we have identified a transition boundary.

For each transition, we compute the cheaper operation:

• Prefix flip cost is i
• Suffix flip cost is n - i

The smaller value is added to the running total.

Finally, after processing all transitions, the function returns the minimum cost.

The implementation uses only a few integer variables and scans the string exactly once, making it highly efficient.

Go Solution

func minimumCost(s string) int64 {
    n := len(s)
    var totalCost int64 = 0

    for i := 1; i < n; i++ {
        if s[i] != s[i-1] {
            leftCost := i
            rightCost := n - i

            if leftCost < rightCost {
                totalCost += int64(leftCost)
            } else {
                totalCost += int64(rightCost)
            }
        }
    }

    return totalCost
}

The Go implementation follows exactly the same logic as the Python version.

One important detail is the use of int64 for the return type and accumulated cost. Since the total cost can become large when n approaches 100000, using int64 ensures there is no overflow risk.

String indexing in Go directly accesses bytes, which works perfectly here because the string contains only ASCII characters '0' and '1'.

Worked Examples

Example 1

Input:

s = "0011"

String length:

n = 4

We scan adjacent pairs.

i	s[i-1]	s[i]	Transition?	min(i, n-i)	Total Cost
1	0	0	No	-	0
2	0	1	Yes	min(2, 2) = 2	2
3	1	1	No	-	2

Final answer:

2

Example 2

Input:

s = "010101"

String length:

n = 6

We scan adjacent pairs.

i	s[i-1]	s[i]	Transition?	min(i, n-i)	Total Cost
1	0	1	Yes	min(1, 5) = 1	1
2	1	0	Yes	min(2, 4) = 2	3
3	0	1	Yes	min(3, 3) = 3	6
4	1	0	Yes	min(4, 2) = 2	8
5	0	1	Yes	min(5, 1) = 1	9

Final answer:

9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the string and processes each adjacent pair exactly once. No additional data structures proportional to the input size are needed.

This efficiency is ideal for the constraint n <= 100000.

Test Cases

sol = Solution()

# Provided examples
assert sol.minimumCost("0011") == 2  # Single transition
assert sol.minimumCost("010101") == 9  # Alternating pattern

# Already uniform strings
assert sol.minimumCost("0") == 0  # Single character
assert sol.minimumCost("1") == 0  # Single character
assert sol.minimumCost("00000") == 0  # All zeros
assert sol.minimumCost("11111") == 0  # All ones

# Single transition cases
assert sol.minimumCost("01") == 1  # Cheapest suffix or prefix
assert sol.minimumCost("10") == 1  # Symmetric case

# Multiple transitions
assert sol.minimumCost("101") == 2  # Two transitions
assert sol.minimumCost("0110") == 3  # Transitions in middle

# Alternating patterns
assert sol.minimumCost("0101") == 4  # Frequent transitions
assert sol.minimumCost("101010") == 9  # Larger alternating case

# Large grouped sections
assert sol.minimumCost("000111000") == 6  # Two transitions
assert sol.minimumCost("111000111") == 6  # Symmetric grouping

# Edge-heavy transitions
assert sol.minimumCost("100000") == 1  # Transition near start
assert sol.minimumCost("000001") == 1  # Transition near end

Test	Why
"0011"	Validates basic transition handling
"010101"	Tests many alternating transitions
"0"	Smallest possible input
"00000"	Already uniform string
"01"	Single transition case
"101"	Multiple small transitions
"0110"	Transition in central region
"000111000"	Multiple grouped segments
"100000"	Cheapest operation near beginning
"000001"	Cheapest operation near end

Edge Cases

Single Character Strings

A string of length 1 is already uniform because there is only one character. A buggy implementation might incorrectly attempt operations or access invalid indices during adjacent comparisons.

This implementation handles the case naturally because the loop starts at index 1. For a length 1 string, the loop never executes, and the function correctly returns 0.

Already Uniform Strings

Strings like "000000" or "11111" contain no transitions. Some incorrect approaches may unnecessarily perform operations even though the string already satisfies the requirement.

Our algorithm only adds cost when adjacent characters differ. Since no transitions exist, the total cost remains 0.

Alternating Patterns

Strings such as "010101010" contain the maximum possible number of transitions. These cases stress whether the algorithm correctly accumulates contributions from every boundary.

The implementation processes each transition independently and adds the minimum boundary-fixing cost each time, guaranteeing correctness even in highly fragmented strings.

Transitions Near the Ends

Cases like "100000" or "000001" are important because the cheapest operation is usually the one affecting only a single character.

For example, in "100000", fixing the transition near the beginning costs only 1, because flipping the first character alone is cheaper than flipping almost the entire suffix.

The algorithm correctly computes:

min(i, n - i)

which naturally favors the smaller side.