aboutsummaryrefslogtreecommitdiff
path: root/flip_string_monotone_increase.cpp
blob: 35e0e0ccf078c30714b594aa82eb65d6edb6387b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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
}