Math Dynamic Programming
Intermediate Level

Implement the minimumFlipsMonotoneBinary method that returns the minimum flips needed to make a binary string monotone increasing.

You are given a binary string containing only 0 and 1. A monotone increasing binary string has all zeroes before all ones, such as 000111, 000, or 111.

Return the minimum number of character flips required to make the string monotone increasing.

Example 1
Input:
text (string) = 110
Return:
(int) 1
Example 2
Input:
text (string) = 10110
Return:
(int) 2
Example 3
Input:
text (string) = 11000
Return:
(int) 2

Scan the string and track how many ones have appeared and how many flips are currently needed.

When a 1 is found, it may stay as part of the final ones section. When a 0 appears after some ones, there are two choices: flip this zero to one, or flip all previous ones to zero. Keep the cheaper choice.

This gives the minimum flips in one pass.

Pseudocode:

function minimumFlipsMonotoneBinary(text):
    ones = 0
    flips = 0
    for each character ch in text:
        if ch == '1':
            ones++
        else:
            flips = min(flips + 1, ones)
    return flips
Run your code to see the result.