> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/flip-string-to-monotone-increasing.md).

# Flip String to Monotone Increasing

<https://leetcode.com/problems/flip-string-to-monotone-increasing/>

> We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
>
> Return the minimum number of flips to make S monotone increasing.
>
> Example 1:
>
> Input: "00110"
>
> Output: 1
>
> Explanation: We flip the last digit to get 00111.
>
> Example 2:
>
> Input: "010110"
>
> Output: 2
>
> Explanation: We flip to get 011111, or alternatively 000111.
>
> Example 3:
>
> Input: "00011000"
>
> Output: 2
>
> Explanation: We flip to get 00000000.
>
> Note:
>
> 1 <= S.length <= 20000
>
> S only consists of '0' and '1' characters.

## Thoughts

单调增只能是00…11…。因此是从某位开始后面都是1时需要翻转(0和1值对调)次数最少即答案。 可以用类似dp的思想，让f(i)表示前i个数组元素维持单调增需要的最少翻转次数。假设我们要翻转的是1之后的0，观察到当1之后0数目大于1的数目时，此时把前面的1翻转成0次数要更小。这个性质在数组任何位置都正确。比如0010011000，当到了第一个1后面的第二个0时，应当把第一个1翻成0，这样当前子数组还是单调增的，因此f(4) = 2。剩下的11000同理，经过f(6) = f(5) = f(4), f(7) = f(4) + 1(翻转第一个0为1)， f(8) = f(7) + 1 (翻转第二个0)，但f(9)此时1后面的0比1多，应当翻转前两个1，因此f(9) = f(4) + 2 = 4. f数组只是帮助理解，并不需要真的一个数组，只要两个变量分别记录当前位置时前面和现在的1个数，以及当前位置应当翻转的个数（默认为1后0的个数，当超过1的个数时，替换成1的个数）。

## Code

```
class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int flips = 0, ones = 0;
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == '0') {
                if (ones == 0) continue;
                ++flips;
            } else {
                ++ones;
            }
            if (flips > ones) flips = ones;
        }
        return flips;
    }
};
```

## Analysis

TC：O(N), OC: O(1).