Flip String to Monotone Increasing LeetCode solution in Python

1
class Solution:
2
    def minFlipsMonoIncr(self, s: str) -> int:
3
        n = len(s)
4
        min_flip = n
5
        one_left = 0
6
        # zero_right = 0
7
        # for c in s:
8
        #     if c == "0":
9
        #         zero_right += 1
10

11
        zero_right = s.count(
12
            "0"
13
        )  # since we will start with 11...11 then every zero in s will be on the right side of the border
14

15
        # for each i imagine that we have the borderline at i index any index >= i will be 1 and index < i will be 0.
16
        # i = 0, n = 5 -> 11111
17
        # i = 1, n = 5 -> 01111
18
        # i = 5        -> 00000
19
        for i in range(n + 1):
20
            # the number of flip will be equal number of 1 on the left side of the border + number of zero on the right side of the border
21
            # from example     00110
22
            #                    v
23
            # comparing with   00111  : i = 2, one_left = 0, zero_right = 1, then we have to do 0 + 1 flip in this i
24
            min_flip = min(min_flip, one_left + zero_right)
25

26
            # edge case for i = n or all zero (00...00)
27
            if i == len(s):
28
                continue
29
            # reduce count of zero_right when 0 is moving to the 0-zone or left side of border
30
            if s[i] == "0":
31
                zero_right -= 1
32
            else:
33
                one_left += (
34
                    1  # increase one on the left side when we move 1 into the left side
35
                )
36

37
        return min_flip