# LeetCode 926: Flip String to Monotone Increasing

## Problem Restatement

We are given a binary string `s`.

Each character is either `'0'` or `'1'`.

A binary string is monotone increasing when all `0`s come before all `1`s. It may contain only `0`s, only `1`s, or both.

Valid examples:

```python
"000"
"111"
"000111"
"001111"
```

Invalid examples:

```python
"10"
"101"
"010"
```

We may flip any character:

```text
0 -> 1
1 -> 0
```

Return the minimum number of flips needed to make `s` monotone increasing. The official statement gives examples such as `"00110" -> 1`, `"010110" -> 2`, and `"00011000" -> 2`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A binary string `s` |
| Output | Minimum number of flips |
| Constraint | `1 <= s.length <= 10^5` |
| Characters | Each character is `'0'` or `'1'` |

Function shape:

```python
class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ...
```

## Examples

Example 1:

```python
s = "00110"
```

The string is almost monotone increasing.

We can flip the last character:

```text
00110 -> 00111
```

That takes `1` flip.

So the answer is:

```python
1
```

Example 2:

```python
s = "010110"
```

One valid result is:

```text
010110 -> 011111
```

Another valid result is:

```text
010110 -> 000111
```

Both take `2` flips.

So the answer is:

```python
2
```

Example 3:

```python
s = "00011000"
```

We can flip the two `1`s into `0`s:

```text
00011000 -> 00000000
```

That takes `2` flips.

So the answer is:

```python
2
```

## First Thought: Try Every Split

A monotone increasing binary string has one split point:

```text
000...000111...111
```

Everything before the split should be `0`.

Everything after the split should be `1`.

So one direct solution is to try every possible split.

For each split:

1. Count how many `1`s appear on the left.
2. Count how many `0`s appear on the right.
3. Flip those characters.

For example:

```text
s = "010110"
```

If we choose the split after the third character:

```text
010 | 110
```

The left side should be all `0`s, so the `1` on the left must be flipped.

The right side should be all `1`s, so the `0` on the right must be flipped.

Total flips:

```text
1 + 1 = 2
```

This idea works, but scanning both sides for every split would be too slow.

## Key Insight

We can process the string from left to right and keep only two values:

| Variable | Meaning |
|---|---|
| `ones` | Number of `1`s seen so far |
| `flips` | Minimum flips needed to make the prefix monotone increasing |

When we see a `1`, it already fits the increasing order. We can keep it and increment `ones`.

When we see a `0`, there is a conflict if previous `1`s exist.

For this `0`, we have two choices:

1. Flip this `0` to `1`.
2. Keep this `0`, but flip all previous `1`s to `0`.

So the recurrence is:

```python
flips = min(flips + 1, ones)
```

Meaning:

| Choice | Cost |
|---|---|
| Flip current `0` to `1` | `flips + 1` |
| Keep current `0`, flip previous `1`s | `ones` |

## Algorithm

Initialize:

```python
ones = 0
flips = 0
```

Then scan each character `c` in `s`.

If `c == '1'`:

```python
ones += 1
```

If `c == '0'`:

```python
flips = min(flips + 1, ones)
```

Finally return:

```python
flips
```

## Walkthrough

Use:

```python
s = "010110"
```

Start:

```text
ones = 0
flips = 0
```

| Character | Meaning | `ones` | `flips` |
|---|---|---:|---:|
| `0` | Already valid as a leading zero | 0 | 0 |
| `1` | Keep it | 1 | 0 |
| `0` | Flip this `0`, or flip previous `1` | 1 | 1 |
| `1` | Keep it | 2 | 1 |
| `1` | Keep it | 3 | 1 |
| `0` | Flip this `0`, or flip previous `1`s | 3 | 2 |

The answer is:

```python
2
```

## Correctness

At every position, `flips` stores the minimum number of flips needed to make the prefix ending at that position monotone increasing.

When the current character is `1`, appending it to a monotone increasing prefix keeps the prefix valid, because `1` may appear after `0`s or after other `1`s. So `flips` does not change.

When the current character is `0`, appending it after previous `1`s may break monotone order. There are exactly two valid ways to repair this:

1. Flip the current `0` into `1`, which costs `flips + 1`.
2. Keep the current `0`, which means every previous `1` must become `0`, costing `ones`.

The algorithm takes the smaller of these two choices.

These two choices cover all valid monotone forms for the current prefix. Therefore, after each character, `flips` remains the minimum possible cost for that prefix.

After the final character, the prefix is the whole string, so `flips` is the minimum number of flips needed for the whole string.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the string once |
| Space | `O(1)` | We store only two counters |

## Implementation

```python
class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        ones = 0
        flips = 0

        for c in s:
            if c == "1":
                ones += 1
            else:
                flips = min(flips + 1, ones)

        return flips
```

## Code Explanation

`ones` counts how many `1`s we have seen so far.

```python
ones = 0
```

`flips` stores the best answer for the prefix processed so far.

```python
flips = 0
```

When we see a `1`, it can stay where it is.

```python
if c == "1":
    ones += 1
```

When we see a `0`, it may violate the monotone increasing order if earlier `1`s exist.

```python
flips = min(flips + 1, ones)
```

`flips + 1` means we flip the current `0` into `1`.

`ones` means we keep the current `0`, but flip all previous `1`s into `0`.

The smaller value gives the best result for the current prefix.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minFlipsMonoIncr("00110") == 1
    assert s.minFlipsMonoIncr("010110") == 2
    assert s.minFlipsMonoIncr("00011000") == 2
    assert s.minFlipsMonoIncr("0") == 0
    assert s.minFlipsMonoIncr("1") == 0
    assert s.minFlipsMonoIncr("00000") == 0
    assert s.minFlipsMonoIncr("11111") == 0
    assert s.minFlipsMonoIncr("111000") == 3
    assert s.minFlipsMonoIncr("101010") == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"00110"` | Official basic case |
| `"010110"` | Has several possible optimal results |
| `"00011000"` | Best answer flips `1`s to `0`s |
| `"0"` | Minimum length |
| `"1"` | Minimum length |
| `"00000"` | Already monotone |
| `"11111"` | Already monotone |
| `"111000"` | Fully decreasing blocks |
| `"101010"` | Alternating pattern |