926. Flip String to Monotone Increasing | 1602

 1class Solution:
 2    def minFlipsMonoIncr(self, s: str) -> int:
 3        # 1 -> 0 from beginning
 4        # 0 -> 1 from end
 5        # 000110001 (answer should be 2)
 6        # 000122223 ->
 7        # 654333210 <-
 8        # 543454323 nope
 9
10        # first `1` and the last `0`?
11        # 000110001
12        #    x   y
13        # 3 zeros after x, 2 ones before y
14        # 010110
15        #  x   y
16        # 2 zeros after x, 3 ones before y
17        # 00011000
18        #    x   y
19        # 3 zeros after x, 2 ones before y
20
21        # wrong answer:
22        # 10011111110010111011 (should return 5)
23        # x                y
24        # x12       34 5   6
25        #    ..98765  4 321y
26        # 1         23 4   5
27
28        # wrong implementation:
29
30        first_one = s.find("1")
31        last_zero = s.rfind("0")
32
33        if first_one == -1 or last_zero == -1:
34            return 0
35
36        return min(Counter(s[first_one:])["0"], Counter(s[:last_zero])["1"])

 1class Solution:
 2    def minFlipsMonoIncr(self, s: str) -> int:
 3        # general idea:
 4
 5        # When you see a '1', do you ever need to flip it immediately to keep the prefix monotone increasing? Why or why not?
 6
 7        # suppose you encounter a '0' after you've already seen some '1's. To keep the prefix monotone, you have two choices—what are they, and what’s the cost of each in terms of `ones` and `flips` so far?
 8
 9        # result:
10        # when you see a '0': flips = min(flips+1, ones)
11        # when you see a '1': ones += 1
12
13        flips = 0
14        ones = 0
15
16        for c in s:
17            if c == "0":
18                flips = min(flips + 1, ones)
19            else:
20                ones += 1
21
22        return flips  # while iterating, flips _always_ keeps track of the **minimum flips** that will make s[0:now] legal