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
iand invert all characters from index0to indexi, both inclusive, with a cost ofi + 1. - Choose an index
iand invert all characters from indexito indexn - 1, both inclusive, with a cost ofn - 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
2Apply 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
Input
s = "010101"Output
9The 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'