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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Make All Characters Equal

Number: 2817

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed binary string s of length n, you may perform two kinds of inversion operations: • Invert every character from index 0 to a chosen index i (inclusive) for a cost of i+1. • Invert every character from a chosen index i to index n–1 (inclusive) for a cost of n–i. Return the minimum cost required to make all characters of s equal (either all '0's or all '1's).

Key Insights

  • Every change between two adjacent characters (a “boundary”) forces a decision: the inversion that will flip one of the two contiguous parts.
  • There are two ways to “fix” a boundary: • Flip the prefix ending at the boundary (cost = index+1). • Flip the suffix starting immediately after the boundary (cost = n–(index+1)).
  • In an optimal sequence of operations the boundaries do not “overlap” in their necessity; one may essentially pay a cost at each transition.
  • The overall answer turns out to be the sum (over every adjacent pair where s changes) of the minimum cost among the two available operations at that boundary.
  • Note that if s is already uniform then there is no boundary and the cost is 0.

Space and Time Complexity

Time Complexity: O(n), since we do a single pass scanning adjacent characters. Space Complexity: O(1), as only a few counters are needed.

Solution

We can show that in any optimal sequence of flips making s uniform, each “transition” (where s[i] ≠ s[i+1]) must be “resolved” by at least one flip. Because the only allowed operations invert either a prefix or a suffix, when a boundary is encountered at index i we have two choices: • Perform a prefix flip ending at index i with a cost of i+1. • Perform a suffix flip starting at index i+1 with a cost of n–(i+1). Thus, for that boundary the best we can do is to add cost = min(i+1, n–i–1). Then the total minimum cost is the sum of these contributions over all boundaries. This greedy deduction works because one may “align” the operations so that each change forces exactly one inversion (without “double‐paying” for overlapping intervals). Finally, the answer is the minimum cost to get s into one uniform state – note that if s is already uniform, no operation (and no transition) is needed.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def minCost(self, s: str) -> int:
        n = len(s)
        total_cost = 0
        # Traverse the string to find boundaries where character changes
        for i in range(n - 1):
            if s[i] != s[i+1]:
                # boundary at index i between s[i] and s[i+1]
                # Option 1: flip prefix ending at index i: cost = i+1
                # Option 2: flip suffix starting at index i+1: cost = n - (i+1)
                total_cost += min(i + 1, n - i - 1)
        return total_cost

# Example Usage:
# sol = Solution()
# print(sol.minCost("0011"))  # Output: 2
← Back to All Questions