## 926. Flip String to Monotone Increasing

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. `1 <= S.length <= 20000`
2. `S` only consists of `'0'` and `'1'` characters.

## Rust Solution

``````struct Solution;

impl Solution {
fn min_flips_mono_incr(s: String) -> i32 {
let n = s.len();
let s: Vec<char> = s.chars().collect();
let mut left = vec![0; n];
let mut ones = 0;
let mut right = vec![0; n];
let mut zeros = 0;
for i in 0..n {
left[i] = ones;
if s[i] == '1' {
ones += 1;
}
}
for i in (0..n).rev() {
right[i] = zeros;
if s[i] == '0' {
zeros += 1;
}
}
let mut res = std::i32::MAX;
for i in 0..n {
res = res.min(left[i] + right[i]);
}
res
}
}

#[test]
fn test() {
let s = "00110".to_string();
let res = 1;
assert_eq!(Solution::min_flips_mono_incr(s), res);
let s = "010110".to_string();
let res = 2;
assert_eq!(Solution::min_flips_mono_incr(s), res);
let s = "00011000".to_string();
let res = 2;
assert_eq!(Solution::min_flips_mono_incr(s), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.