:type S: str :rtype: int
(self, S)
| 45 | |
| 46 | class Solution(object): |
| 47 | def minFlipsMonoIncr(self, S): |
| 48 | """ |
| 49 | :type S: str |
| 50 | :rtype: int |
| 51 | """ |
| 52 | |
| 53 | x = [0] if S[0] == '0' else [1] |
| 54 | |
| 55 | # left to right |
| 56 | # 1 -> 0 |
| 57 | for i in range(1, len(S)): |
| 58 | if S[i] == '1': |
| 59 | x.append(x[-1]+1) |
| 60 | else: |
| 61 | x.append(x[-1]) |
| 62 | |
| 63 | # right to left |
| 64 | # 0 -> 1 |
| 65 | S = S[::-1] |
| 66 | y = [0] if S[0] == '1' else [1] |
| 67 | for i in range(1, len(S)): |
| 68 | if S[i] == '0': |
| 69 | y.append(y[-1]+1) |
| 70 | else: |
| 71 | y.append(y[-1]) |
| 72 | |
| 73 | y.reverse() |
| 74 | |
| 75 | return min([i+j for i,j in zip(x,y)]) - 1 |
| 76 |