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.
The solution to the Above Question
class Solution {
public:
int minFlipsMonoIncr(string s) {
int zero=0;
int change=0;
int i=0;
while(s[i]=='0'){
i++;
}
while(i<s.length()){
if(s[i]=='0'){
zero++;
}
if(s[i]=='1'){
change++;
}
if(zero>change){
change=zero;
}
i++;
}
return change;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.