Minimum Cost to Make All Characters Equal — LeetCode 2712 Python Solution

The problem

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

Input

s = "0011"

Output

2

Explanation

Apply the second operation with i = 2 to obtain s = "0000" for a cost of 2. It can be shown that 2 is the minimum cost to make all characters equal.

Python solution

class Solution:
    def minimumCost(self, s: str) -> int:
        ans, n = 0, len(s)
        for i in range(1, n):
            if s[i] != s[i - 1]:
                ans += min(i, n - i)
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2712. Minimum Cost to Make All Characters Equal is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems