Minimum number of flips of binary bit (0 or 1)

minimum_bit_flips.py

from collections import Counter


def getMinFlips(pwd):
    # O(n)
    zeroCounter = Counter()
    reverseOnesCounter = Counter()
    n = len(pwd)
    if n % 2 != 0:
        return 0
    if n == 2:
        if len(set(pwd)) == 1:
            return 0
        else:
            return 1

    for i in range(0, n):
        # count zero incrementally in fwd direction
        zeroCounter[i] += zeroCounter[i - 1] + (1 if pwd[i] == "0" else 0)
        j = n - i - 1
        # count 1s incrementally in bwd direction
        reverseOnesCounter[j] += reverseOnesCounter[j + 1] + (1 if pwd[j] == "1" else 0)

    minSoFar = sys.maxsize
    for k in range(2, n, 2):
        minSoFar = min(minSoFar,
                       min(
                           # pwd[:k] -> all 1s , pwd[k:] -> all 0s
                           zeroCounter[k] + reverseOnesCounter[k],
                           # pwd[:k] -> all 0s , pwd[k:] -> all 1s
                           (k - zeroCounter[k]) + (n - k - reverseOnesCounter[k])))
    return minSoFar