We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Make All Characters Equal

Difficulty: Medium

Problem Description

You are given a 0-indexed binary string s of length n on which you can apply two types of operations:

  1. Choose an index i and invert all characters from index 0 to index i (both inclusive), with a cost of i + 1.
  2. 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.

Key Insights

  • Inverting a character means changing '0' to '1' and vice-versa.
  • The two operations allow for flexibility in choosing which characters to invert based on their positions.
  • The cost of each operation depends on the index chosen, making it crucial to evaluate the costs effectively.
  • A greedy approach can be used to minimize costs by calculating the cost for making all characters '0' and all characters '1', and then taking the minimum of the two.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can approach it by calculating the cost to convert the entire string to '0's and the cost to convert it to '1's.

  1. Iterate through the string and keep track of the number of '1's and '0's encountered.
  2. For each character in the string, calculate the cost of making the characters before it equal to '0's or '1's based on the two operations.
  3. The first operation will cost (index + 1) for each '1' we encounter when trying to make the string all '0's.
  4. The second operation will cost (n - index) for each '0' we encounter when trying to make the string all '1's.
  5. Finally, return the minimum of the total costs calculated for both scenarios.

Code Solutions

def minCost(s: str) -> int:
    n = len(s)
    cost_to_zero = 0
    cost_to_one = 0
    count_ones = 0
    count_zeros = 0
    
    # Calculate cost to make all characters '0'
    for i in range(n):
        if s[i] == '1':
            count_ones += 1
            cost_to_zero += (i + 1)
    
    # Calculate cost to make all characters '1'
    for i in range(n):
        if s[i] == '0':
            count_zeros += 1
            cost_to_one += (n - i)
    
    return min(cost_to_zero, cost_to_one)
← Back to All Questions