Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 17

Description

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.

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  int minFlipsMonoIncr(string s) {
    int ones = 0;
    int len = s.length();
    for(auto c : s) {
      ones += (c & 1);
    }
    int zeros = len - ones;
    int currentOnes = 0;
    int currentZeros = 0;
    int answer = zeros;
    for(auto c : s) {
      currentZeros += !(c & 1);
      currentOnes += (c & 1);
      answer = min(answer, currentOnes + zeros - currentZeros);
    }
    return answer;
  }
};

// Accepted
// 93/93 cases passed (9 ms)
// Your runtime beats 99.49 % of cpp submissions
// Your memory usage beats 52.66 % of cpp submissions (11.2 MB)