aboutsummaryrefslogtreecommitdiff
path: root/other/flip_string_monotone_increase.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/flip_string_monotone_increase.cpp')
-rw-r--r--other/flip_string_monotone_increase.cpp36
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
+}