# Minimum Cost to Make All Characters Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-cost-to-make-all-characters-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-make-all-characters-equal
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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 <= 105`
* `s[i]` is either `'0'` or `'1'`

# Approaches
## Brute-Force with Graph Search
This approach models the problem as finding the shortest path in a state-space graph. Each possible binary string is a node, and an operation is a weighted edge connecting two nodes. We can use a graph search algorithm like Dijkstra's to find the minimum cost path from the initial string `s` to any uniform string (all '0's or all '1's).
**Time:** O(n^2 * 2^n), The state space is V = 2^n. From each state, there are E = O(n) transitions. Each transition involves O(n) work for string manipulation. Dijkstra's would be O(E log V) or O(E+V log V) depending on implementation, leading to a complexity that is exponential in n. · **Space:** O(n * 2^n), to store the minimum costs for all possible 2^n strings of length n.
**Pros:** Guaranteed to find the optimal solution if it could run to completion.; It's a direct application of a well-known algorithm.
**Cons:** Extremely inefficient in both time and space.; The number of states (2^n) makes it infeasible for the given constraints (n <= 10^5).; String manipulation and storage are very expensive.
### Explanation
The state in our search is the current string, and the cost is the accumulated cost of operations. We use a priority queue to always explore the state with the minimum accumulated cost first, which is the core of Dijkstra's algorithm. A map or hash table is used to keep track of the minimum cost found so far for each string to avoid cycles and redundant computations.

The algorithm starts with the initial string `s` and a cost of 0. In each step, it extracts the string with the lowest cost from the priority queue. If this string is uniform, we have found the minimum cost. Otherwise, it generates all possible next strings by applying each of the `2n` operations (prefix flips for `i=0..n-1` and suffix flips for `i=0..n-1`). For each new string, if a cheaper path to it is found, its cost is updated, and it's added to the priority queue.

```java
// This approach is purely theoretical for the given constraints and would time out.
// A full implementation is impractical due to the massive state space.
class Solution {
    // Conceptual structure of a brute-force Dijkstra's approach.
    public long minimumCost(String s) {
        int n = s.length();
        PriorityQueue<Pair<Long, String>> pq = new PriorityQueue<>(Comparator.comparingLong(Pair::getKey));
        Map<String, Long> minCosts = new HashMap<>();

        pq.add(new Pair<>(0L, s));
        minCosts.put(s, 0L);

        while (!pq.isEmpty()) {
            Pair<Long, String> current = pq.poll();
            long cost = current.getKey();
            String currentS = current.getValue();

            if (isUniform(currentS)) {
                return cost;
            }

            if (cost > minCosts.get(currentS)) {
                continue;
            }

            // Explore all 2n possible operations
            for (int i = 0; i < n; i++) {
                // ... logic to apply prefix and suffix flips ...
                // ... update pq and minCosts if a cheaper path is found ...
            }
        }
        return -1; // Should not be reached
    }

    private boolean isUniform(String s) {
        if (s.length() <= 1) return true;
        char first = s.charAt(0);
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != first) return false;
        }
        return true;
    }
}
```
### Algorithm
- Model the problem as a shortest path problem on a graph.
- Each unique binary string of length `n` is a node in the graph.
- An edge exists between two string nodes if one can be transformed into the other by a single operation. The weight of the edge is the cost of that operation.
- Use Dijkstra's algorithm to find the shortest path from the initial string `s` to any uniform string (all '0's or all '1's).
- Use a priority queue to explore states with the lowest cost first and a hash map to store minimum costs to visited states to avoid cycles.

## Dynamic Programming
This approach uses dynamic programming based on a key insight: the total cost is the sum of costs to fix each "change point" where adjacent characters are different. An operation either fixes a single change point or doesn't affect any. This allows us to build up the solution iteratively.
**Time:** O(n), due to the single loop through the string of length n. · **Space:** O(n) for the DP array.
**Pros:** Much more efficient than brute-force.; Correctly identifies the independent nature of solving each mismatch.; Provides a clear, structured way to think about the problem.
**Cons:** Uses O(n) extra space for the DP array, which is not strictly necessary.
### Explanation
The core idea is that to make the string uniform, we must eliminate all indices `i` where `s[i] != s[i+1]`. To resolve such a mismatch, we must apply an operation that splits `i` and `i+1`. The two choices are a prefix flip up to `i` (cost `i+1`) or a suffix flip from `i+1` (cost `n-(i+1)`). Since fixing one mismatch doesn't create or resolve another, we can consider each mismatch independently and choose the cheaper operation for each.

We can define a DP state `dp[i]` as the minimum cost to resolve all mismatches in the prefix `s[0...i]`. We build the solution from left to right.

```java
class Solution {
    public long minimumCost(String s) {
        int n = s.length();
        if (n <= 1) {
            return 0;
        }

        // dp[i] stores the minimum cost to make the prefix s[0...i] uniform.
        long[] dp = new long[n];
        dp[0] = 0; // A single character prefix is always uniform.

        for (int i = 1; i < n; i++) {
            // Start with the cost to make the previous prefix uniform.
            dp[i] = dp[i-1];
            
            // If there is a mismatch between s[i] and s[i-1], we must fix it.
            if (s.charAt(i) != s.charAt(i-1)) {
                // To fix the mismatch at index i-1, we need an operation that
                // splits i-1 and i.
                // Option 1: Prefix flip up to i-1. Cost = (i-1) + 1 = i.
                // Option 2: Suffix flip from i. Cost = n - i.
                long costToFix = Math.min(i, n - i);
                dp[i] += costToFix;
            }
        }

        return dp[n - 1];
    }
}
```
### Algorithm
- The key insight is that the total cost is the sum of costs to fix each position `i` where `s[i] != s[i+1]`.
- For each such "mismatch", we must perform an operation that flips one of the characters but not the other. The two options are a prefix flip up to `i` (cost `i+1`) or a suffix flip from `i+1` (cost `n-(i+1)`).
- We can use dynamic programming. Let `dp[i]` be the minimum cost to make the prefix `s[0...i]` uniform.
- The recurrence relation is: `dp[i] = dp[i-1]` if `s[i] == s[i-1]`, and `dp[i] = dp[i-1] + min(i, n-i)` if `s[i] != s[i-1]`.
- The base case is `dp[0] = 0`.
- The final answer is `dp[n-1]`.

## Single Pass Iterative Approach
This is a space-optimized version of the dynamic programming approach. Since the calculation for the current step only depends on the result from the previous step, we don't need to store the entire DP array. We can use a single variable to accumulate the total cost as we iterate through the string once.
**Time:** O(n), as we iterate through the string exactly once. · **Space:** O(1), as we only use a few variables to store the cost and loop index, regardless of the input size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Simple, intuitive, and easy to implement.
**Cons:** There are no significant cons to this approach as it is optimal.
### Explanation
This approach is built on the same fundamental insight as the DP solution: the total minimum cost is the sum of the minimum costs to resolve each individual mismatch between adjacent characters. A mismatch occurs at index `i-1` if `s[i-1] != s[i]`. To resolve this, we must apply an operation that flips one character but not the other. The two options are:
1. A prefix flip up to `i-1`, with cost `(i-1) + 1 = i`.
2. A suffix flip from `i`, with cost `n - i`.

The minimum cost to resolve this specific mismatch is `min(i, n - i)`. Since these choices are independent for each mismatch, we can simply iterate through the string, find all mismatches, calculate the minimum cost for each, and sum them up. We use a single variable, `totalCost`, to keep a running sum, which optimizes space.

```java
class Solution {
    public long minimumCost(String s) {
        int n = s.length();
        long totalCost = 0;

        // Iterate through the string to find adjacent characters that are different.
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i-1)) {
                // A mismatch at index i-1 needs to be fixed.
                // We can either flip the prefix ending at i-1 (cost i)
                // or flip the suffix starting at i (cost n-i).
                // We choose the cheaper of the two operations.
                totalCost += Math.min(i, n - i);
            }
        }

        return totalCost;
    }
}
```
### Algorithm
- Initialize `totalCost = 0`.
- Iterate through the string from the second character (`i = 1` to `n-1`).
- At each position `i`, compare `s.charAt(i)` with `s.charAt(i-1)`.
- If they are different, it means there is a mismatch that must be resolved.
- The cost to resolve this mismatch is the minimum of flipping the prefix `s[0...i-1]` (cost `i`) or flipping the suffix `s[i...n-1]` (cost `n-i`).
- Add `min(i, n - i)` to `totalCost`.
- After the loop finishes, `totalCost` will hold the total minimum cost.

# Solutions
### Java

```java
class Solution {
public
  long minimumCost(String s) {
    long ans = 0;
    int n = s.length();
    for (int i = 1; i < n; ++i) {
      if (s.charAt(i) != s.charAt(i - 1)) {
        ans += Math.min(i, n - i);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumCost(string s) {
    long long ans = 0;
    int n = s.size();
    for (int i = 1; i < n; ++i) {
      if (s[i] != s[i - 1]) {
        ans += min(i, n - i);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumCost(self, s: str) -> int: ans, n = 0, len(s) for i in range(1, n): if s[i] != s[i - 1]: ans += min(i, n - i) return ans

```