Minimum Cost to Make All Characters Equal

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
Inputs = "0011"
Output2
Apply the second operation with i = 2 to obtain s = "0000" for a cost of 2, which is the minimum cost to make all characters equal.
Example 2
Inputs = "010101"
Output9
The described sequence of operations costs 3 + 2 + 1 + 2 + 1 = 9, which is the minimum cost to make all characters equal.

Constraints

  • 1 <= s.length == n <= 10^5
  • s[i] is either '0' or '1'

Asked at 1 companies

</>

Your Solution

(Ctrl/Cmd + Enter)

Switching Language

Loading template...

Loading...

Sign in to save your progress

AI code evaluation

Get a correctness verdict, missed edge cases, and complexity analysis of your solution.

Sign in to evaluate