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) =
110Returns (int)
1Example 2
Input
text (string) =
10110Returns (int)
2Example 3
Input
text (string) =
11000Returns (int)
2Scan 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 flipsReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run