diff options
Diffstat (limited to 'other/flip_string_monotone_increase.cpp')
-rw-r--r-- | other/flip_string_monotone_increase.cpp | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/other/flip_string_monotone_increase.cpp b/other/flip_string_monotone_increase.cpp new file mode 100644 index 0000000..35e0e0c --- /dev/null +++ b/other/flip_string_monotone_increase.cpp @@ -0,0 +1,36 @@ +#include "leetcode.h" + +/* + * a binary string is monotone increasing if it consists of some number + * of 0's (none is valid), followed by some number of 1's (none is valid) + * given: binary string 's'. you can flip 's[i]' changing for 0 to 1 or vice + * versa. return the minimum number of flips to make 's' monotone increasing. + */ + +class Solution { +public: + int minFlipsMonoIncr(string s) { + int flips = 0, cnt = 0; + for (auto i : s) { + if (i == '1') + cnt++; + else + flips++; + flips = min(flips, cnt); + } + return flips; + } +}; + +int main() { + Solution obj; + cout << obj.minFlipsMonoIncr("00110") << endl; + // expect: 1 + // flip last digit to get 00111 + cout << obj.minFlipsMonoIncr("010110") << endl; + // expect: 2 + // flip s[1] s[5] to get 000111 + cout << obj.minFlipsMonoIncr("00011000") << endl; + // expect: 2 + // flip s[3] s[4] to get 00000000 +} |