Scale Engineer

Minimum Cost to Make All Characters Equal

Med
#2447Time: 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.
Patterns
Dynamic ProgrammingGreedy
Data structures
String

Prompt

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:

i = 2

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem