Minimum Cost to Make All Characters Equal

MEDIUM

Description

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'

Approaches

Checkout 3 different approaches to solve Minimum Cost to Make All Characters Equal. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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:

A prefix flip up to i-1, with cost (i-1) + 1 = i.
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.

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;
    }
}

Complexity Analysis

Time Complexity: O(n), as we iterate through the string exactly once.Space Complexity: O(1), as we only use a few variables to store the cost and loop index, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Cost to Make All Characters Equal. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Minimum Cost to Make All Characters Equal

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

String