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).