# leetcode\_926

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)

We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.

Return the minimum number of flips to make S monotone increasing.

Example 1:

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

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

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

Note:

1 <= S.length <= 20000 S only consists of '0' and '1' characters.

## Solutions

1. **dynamic programming**
2. `dp1` represents the minimum number of swaps to make the prefix be monotone increasing with the last character(may be swapped) as `1`.

```cpp
class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int dp0 = 0, dp1 = 0;
        for (auto c : S)
            if (c == '0')
                dp1 = min(dp0, dp1) + 1;
            else {
                dp1 = min(dp0, dp1);
                dp0 = dp0 + 1;
            }

        return min(dp0, dp1);
    }
};
```

1. **prefix sum**
2. Iterating all possible i, swap the left side into 0s, nad wap the other side into 1s, these two sides can be 0 sized.

```cpp
class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int n = S.size(), sum = 0;
        vector<int> sums(n + 1);
        for (int i = 0; i < n; i++)
            sums[i + 1] = sum += (S[i] == '1');

        int res = n;
        for (int i = 0; i <= n; i++) {
            int nr0 = (n - i) - (sum - sums[i]);
            res = min(res, sums[i] + nr0);
        }
        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_926.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.