Algorithm
Problem Name: 926. Flip String to Monotone Increasing
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 <= 105s[i]is either'0'or'1'.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int minFlipsMonoIncr(char* S) {
/*
1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 n = 15
0 1 1 1 2 3 4 5 6 7 8 9 9 9 10 11 <- num of 1 ahead
4 4 3 2 2 2 2 2 2 2 2 2 1 0 0 0 <- num of 0 after
4 5 4 3 4 5 ...
*/
int i, n, ones[20001], zeros[20001];
int flip2zero, flip2one, flip, min;
n = 0;
ones[0] = 0;
while (S[n]) {
ones[n + 1] = ones[n] + (S[n] == '1' ? 1 : 0);
}
i = n;
zeros[i --] = 0;
while (i >= 0) {
zeros[i] = zeros[i + 1] + (S[i] == '0' ? 1 : 0);
i --;
}
min = n;
for (i = 0; i < = n; i ++) {
flip = ones[i] + zeros[i]; // at i, ones ahead need to flip to zero
// and zeros after need to flip to one
if (min > flip) min = flip;
}
return min;
}
Input
s = "00110"
Output
1
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const minFlipsMonoIncr = function(s) {
const n = s.length
let res = 0, oneCnt = 0
for(const e of s) {
if(e === '1') oneCnt++
else {
const stayZero = oneCnt
const flipToOne = res + 1
res = Math.min(stayZero, flipToOne)
}
}
return res
};
Input
s = "00110"
Output
1
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minFlipsMonoIncr(self, s):
res = cur = s.count("0")
for c in s: res, cur = c == "1" and (res, cur + 1) or (min(res, cur - 1), cur - 1)
return res
Input
s = "010110"
Output
2