[LeetCode] Flip String to Monotone Increasing

Problem: 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:

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

Approach: A brute force approach is to generate all the binary strings of length n and see the number of flips required for each binary string and return the minimum flips among them but it will be very expensive solution.

Let's look at what we are trying to do here; we are trying to form a binary string which looks like 000...111 that mean x0sy1s so we can say there are x 0s in the left half and y 1s in the right half so ultimately it is the problem of knowing how many 1s are in left half and how many 0s are in the right half and we take the minimum of it.

Implementation in C#:

    public int MinFlipsMonoIncr(string s) 

    {

        int ones = 0;

        int minFlips = 0;

        for (int i = 0; i < s.Length; ++i)

        {

            if (s[i] == '1')

            {

                ++ones;

            }

            else

            {

                minFlips = Math.Min(minFlips + 1, ones);

            }

        }    

        return minFlips;

    }

Complexity: O(n)