Leetcode 926. Flip String to Monotone Increasing

[medium]

Flip String to Monotone Increasing - LeetCode

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.

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

[Java]

1. monotone means the array become “0000001111111”. From left to right, flips minimum times and make the array become monotone.
2. I first thought count 1’s and 0’s from left/ right sides and return the minimum result. However, it’s wrong. We might need to flip ones or zeros depend on the current situation. And that is the reason why we can use DP to get the result.
3. We start on the begining of the String. If there are leading zeros, we can just skip it. Then, count the ones and zeros in the string.
4. If we flips ones and could have a smaller result, we should flips ones instead of zeros. Otherwise, we will flip zeros.
5. return the result.