Flip String to Monotone Increasing LeetCode solution in C++

1
class Solution {
2
 public:
3
  int minFlipsMonoIncr(string s) {
4
    // assume start making 1 from i th index
5
    //  what number of 0s we need to flip at right side
6
    //  what number of 1s we need to flip at left side
7
    //  for this maintain prefix and suffix
8

9
    int n = s.size();
10
    vector<int> noOfZerosToRight(n, 0); // R to L
11
    vector<int> noOfOnesToLeft(n, 0);   // L to R
12

13
    if (s[0] == '1') noOfOnesToLeft[0] = 1;
14
    for (int i = 1; i < n; i++) {
15
      if (s[i] == '1')
16
        noOfOnesToLeft[i] = noOfOnesToLeft[i - 1] + 1;
17
      else
18
        noOfOnesToLeft[i] = noOfOnesToLeft[i - 1];
19
    }
20

21
    if (s[n - 1] == '0') noOfZerosToRight[n - 1] = 1;
22
    for (int i = n - 2; i >= 0; i--) {
23
      if (s[i] == '0')
24
        noOfZerosToRight[i] = noOfZerosToRight[i + 1] + 1;
25
      else
26
        noOfZerosToRight[i] = noOfZerosToRight[i + 1];
27
    }
28

29
    // starting treating i as partition of 0 and 1:
30
    // 0 at the lefts and 1 at the rights including i:
31
    int ans = 1e9;
32
    for (int i = 0; i < n; i++) {
33
      int leftFlips = 0; // when we want all 1s
34
      int rightFlips = noOfZerosToRight[i];
35

36
      if (i - 1 >= 0) leftFlips = noOfOnesToLeft[i - 1];
37
      ans = min(ans, (leftFlips + rightFlips));
38
    }
39

40
    ans = min(ans, noOfOnesToLeft.back() + 0); // when want all 0s
41
    return ans;
42
  }
43
  // O(N) + O(N)
44
};