Leetcode 926. Flip String to Monotone Increasing / 1653. Minimum Deletions to Make String Balanced

[Woodyiiiiiii]

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

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

Example 1:

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

---

这道题很有意思，有两种解法。

第一种解法: 观察规律，利用前缀和思想

这种方法很容易想到。首先易得肯定是在O(n)时间复杂度的情况下找到答案，又是二元字符串，所以很可能用到前缀和的思想，得知任意位置前面或后面0和1的个数。

然后从所有结果出发，为达到这些结果，[1111..1]到[0000..0]，总共n种结果，而这所有结果之间又有联系，很容易找到达成这些结果需要翻转的个数，也就是知道所有可能的答案，找到最小值即可。说明最大/最小值不一定用二分，这里是遍历所有情况

不要直接从题目当前所给的初始字符串出发，否则很难构建所有可能性。要想到前缀和的思想，利用遍历时变化。

class Solution {
    public int minFlipsMonoIncr(String s) {
        int zeroCnt = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                ++zeroCnt;
            }
        }
        int ans = zeroCnt, cnt = ans;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '0') {
                cnt--;
            } else {
                cnt++;
            }
            ans = Math.min(ans, cnt);
        }
        return ans;
    }
}

第二种解法: 动态规划

即然字符串是monotone increasing，那么子字符串也是monotone increasing。所以为了使[0,i]满足条件，就要先使[0,i-1]达成条件。这就暗示了DP思想。

设dp[i]是[0,i)子字符串中需要flip的最小次数，base条件是dp[0]=0。

这种解法来自官方讲解，如下链接地址，很清晰。思路是这样的：从左到右，在满足题目条件的子字符串最后加上1或者0，会有不同的结果，有联系。如果是1，因为字符串已经符合条件了，所以不变；如果是0，则要考虑是否翻转的可能，若翻转，则结果是前面的结果+1，否则要将字符串中所有的1变为0，两者取最小。

这里的出发点直接是dp[i]=最小值。把结果作为DP缓存，从而推导递进函数，应该是普遍的DP思路。强

class Solution {
    public int minFlipsMonoIncr(String s) {
        int ans = 0, num = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '0') {
                ans = Math.min(num, ans + 1);
            } else {
                ++num;
            }
        }
        return ans;
    }
}

总结：

• 第一种方法是枚举所有可能。找到所有能够满足题目条件的字符串，然后找到能够达成的方法要求，然后比较最小
• 第二种方法是动态规划。确定无后效性后，然后找到dp元素的定义，然后定义dp元素间的推导公式

---

• 926. Flip String to Monotone Increasing
• https://leetcode.com/problems/flip-string-to-monotone-increasing/editorial/
• https://leetcode.com/problems/flip-string-to-monotone-increasing/solutions/2912351/flip-string-to-monotone-increasing/

---

类似题目：

• 1653. Minimum Deletions to Make String Balanced
• 2712. Minimum Cost to Make All Characters Equal

class Solution {
    public int minimumDeletions(String s) {
        int aCnt = 0, bCnt = 0;
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                aCnt++;
            } else if (c == 'b') {
                bCnt++;
            }
        }
        int n = s.length(), ans = n;
        ans = Math.min(aCnt, bCnt);
        int aCnt2 = 0, bCnt2 = 0;
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                aCnt2++;
                aCnt--;
            } else if (c == 'b') {
                bCnt2++;
                bCnt--;
            }
            ans = Math.min(ans, bCnt2 + aCnt);
        }
        return ans;
    }
}

Or:

class Solution {
    public int minimumDeletions(String s) {
        int ans = 0, n = s.length();
        int bCnt = 0;
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                ans = Math.min(bCnt, ans + 1);
            } else {
                bCnt++;
            }
        }
        return ans;
    }
}