[LeetCode] 926. Flip String to Monotone Increasing

[grandyang]

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)

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. 1 <= S.length <= 20000
2. S only consists of '0' and '1' characters.

这道题给了我们一个只有0和1的字符串，现在说是可以将任意位置的数翻转，即0变为1，或者1变为0，让组成一个单调递增的序列，即0必须都在1的前面，博主刚开始想的策略比较直接，就是使用双指针分别指向开头和结尾，开头的指针先跳过连续的0，末尾的指针向前跳过连续的1，然后在中间的位置分别记录0和1的个数，返回其中较小的那个。这种思路乍看上去没什么问题，但是实际上是有问题的，比如对于这个例子 "10011111110010111011"，如果按这种思路的话，就应该将所有的0变为1，从而返回6，但实际上更优的解法是将第一个1变为0，将后4个0变为1即可，最终可以返回5，这说明了之前的解法是不正确的。这道题可以用动态规划 Dynamic Programming 来做，需要使用两个 dp 数组，其中 cnt1[i] 表示将范围是 [0, i-1] 的子串内最小的将1转为0的个数，从而形成单调字符串。同理，cnt0[j] 表示将范围是 [j, n-1] 的子串内最小的将0转为1的个数，从而形成单调字符串。这样最终在某个位置使得 cnt0[i]+cnt1[i] 最小的时候，就是变为单调串的最优解，这样就可以完美的解决上面的例子，子串 "100" 的最优解是将1变为0，而后面的 "11111110010111011" 的最优解是将4个0变为1，总共加起来就是5，参见代码如下：
解法一：

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size(), res = INT_MAX;
        vector<int> cnt1(n + 1), cnt0(n + 1);
        for (int i = 1, j = n - 1; j >= 0; ++i, --j) {
            cnt1[i] += cnt1[i - 1] + (S[i - 1] == '0' ? 0 : 1);
            cnt0[j] += cnt0[j + 1] + (S[j] == '1' ? 0 : 1);
        }
        for (int i = 0; i <= n; ++i) res = min(res, cnt1[i] + cnt0[i]);
        return res;
    }
};

我们可以进一步优化一下空间复杂度，用一个变量 cnt1 来记录当前位置时1出现的次数，同时 res 表示使到当前位置的子串变为单调串的翻转次数，用来记录0的个数，因为遇到0就翻1一定可以组成单调串，但不一定是最优解，每次都要和 cnt1 比较以下，若 cnt1 较小，就将 res 更新为 cnt1，此时保证了到当前位置的子串变为单调串的翻转次数最少，并不关心到底是把0变为1，还是1变为0了，其实核心思想跟上面的解法很相近，参见代码如下：
解法二：

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size(), res = 0, cnt1 = 0;
        for (int i = 0; i < n; ++i) {
            (S[i] == '0') ? ++res : ++cnt1;
            res = min(res, cnt1);
        }
        return res;
    }
};

Github 同步地址:

#926

参考资料：

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

https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183851/C%2B%2BJava-4-lines-O(n)-or-O(1)-DP

https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183896/Prefix-Suffix-Java-O(N)-One-Pass-Solution-Space-O(1)

LeetCode All in One 题目讲解汇总(持续更新中...)