DEV Community

Cover image for 926. Flip String to Monotone Increasing
Harsh Rajpal
Harsh Rajpal

Posted on

 

926. Flip String to Monotone Increasing

Problem Statement:

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:

Code:

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int flipCount = 0;
        int oneCount = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                if (oneCount == 0)
                    continue;
                flipCount++;
            } else
                oneCount++;
            if (oneCount < flipCount)
                flipCount = oneCount;
        }
        return flipCount;

    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity:
O(N)
Space Complexity:
O(1)

Top comments (0)

An Animated Guide to Node.js Event Loop

Node.js doesn’t stop from running other operations because of Libuv, a C++ library responsible for the event loop and asynchronously handling tasks such as network requests, DNS resolution, file system operations, data encryption, etc.

What happens under the hood when Node.js works on tasks such as database queries? We will explore it by following this piece of code step by step.