Flip String to Monotone Increasing
Real-world version: Fewest Switch Throws to Settle the RowThe statement here is our own: the same inputs, outputs and technique.
A row of switches reads row, each character '0' for down and '1' for up. One throw changes a single switch, either way.
The row is settled when no switch that is down comes after a switch that is up: all the downs first, then all the ups, and either group may be empty.
Return the fewest throws that settle the row.
Examples
Example 1
- Input
- row = "111000"
- Output
- 3
Three ups then three downs. Throwing all three ups down settles the row, and so does throwing all three downs up, either way three throws. Nothing shorter works, since every up sits before every down.
Example 2
- Input
- row = "0000"
- Output
- 0
Every switch is down, which is already settled.
Example 3
- Input
- row = "10"
- Output
- 1
One up followed by one down. A single throw on either switch settles it.
Constraints
- 1 <= row.length <= 10^5
- Every character of row is '0' or '1'.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def min_flips_mono_incr(row: str) -> int:public int minFlipsMonoIncr(String row)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's