# [LeetCode 926. Flip String to Monotone Increasing ](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/614/week-2-august-8th-august-14th/3876/)
### Daily challenge Aug 10, 2021 (MEDAIN)

>A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).
>
>You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.
>
>Return the minimum number of flips to make s monotone increasing.

:::info
**Example 1:**
**Input:** s = "00110"
**Output:** 1
**Explanation:** We flip the last digit to get 00111.
:::

:::info
**Example 2:**
**Input** s = "010110"
**Output:** 2
**Explanation:** We flip to get 011111, or alternatively 000111.
:::

:::info
**Example 3:**
**Input:** s = "00011000"
**Output:** 2
**Explanation:** We flip to get 00000000.
:::

:::warning
**Constraints:**
* 1 <= s.length <= 105
* s[i] is either '0' or '1'.
:::

---

### Approach 1 : :bulb: + :book:
**`28 ms ( 22.13% )`** **`O(N)`**

* **`one`** 紀錄字串中 `1` 的數量。
**`flip`** 紀錄最少需要翻動幾次。
* 當 **`flip > one`** 時，表示將 `1 -> 0` 是比較好的做法，
> s = "010110001"
> i = 0 -> `one = 0, flip = 1` -> `flip > one` -> `flip = one = 0`。
> i = 1 -> `one = 1, flip = 0`。
> i = 2 -> `one = 1, flip = 1`。
> i = 3 -> `one = 2, flip = 1`。
> i = 4 -> `one = 3, flip = 1`。
> i = 5 -> `one = 3, flip = 2`。
> i = 6 -> `one = 3, flip = 3`。
> i = 7 -> `one = 3, flip = 4` -> `flip > one` -> `flip = one = 3`。
> i = 8 -> `one = 4, flip = 3`。
> 所以只需 **`3次`**，就能變成`Monotone Increasing`。

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int one = 0;
        int flip = 0;
        for(int i=0; i<s.length(); i++){
            if(s[i] == '1') one++;
            else    flip++;
            
            if(flip > one)  flip = one;
        }
        
        return flip;
    }
};