# Flip String to Monotone Increasing
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flip-string-to-monotone-increasing)
Canonical: https://scaleengineer.com/dsa/problems/flip-string-to-monotone-increasing
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
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_.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

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

# Approaches
## Brute Force by Iterating All Split Points
A monotone increasing binary string has a structure of some number of `0`s followed by some number of `1`s. This implies there's a "split point" where the `0`s end and the `1`s begin. A brute-force approach is to try every possible split point, calculate the number of flips needed for that specific split, and then find the minimum among all possibilities.
**Time:** O(n^2) - The outer loop runs `n+1` times. For each iteration, the inner loops scan the entire string to count flips, taking O(n) time. This results in a quadratic time complexity. · **Space:** O(1) - We only use a few variables to store counts and the minimum value, regardless of the input string size.
**Pros:** Simple to understand and implement.; Correctly solves the problem for small inputs.
**Cons:** Highly inefficient due to nested loops.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The algorithm iterates through every possible index `i` from `0` to `n` (where `n` is the string length) as the potential split point. For each `i`, the string is conceptually divided into a prefix `s[0...i-1]` and a suffix `s[i...n-1]`. To make the string monotone increasing with this split, the prefix must consist entirely of `0`s, and the suffix must consist entirely of `1`s. The cost (number of flips) for this split is the count of `1`s in the prefix plus the count of `0`s in the suffix. We calculate this cost for every possible `i` and maintain the minimum cost found. The edge cases `i=0` (target string is all `1`s) and `i=n` (target string is all `0`s) are naturally handled by the loops.

```java
class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int minFlips = Integer.MAX_VALUE;

        // Iterate through all possible split points
        for (int i = 0; i <= n; i++) {
            int currentFlips = 0;
            // Flips for prefix s[0...i-1] to be all '0's
            for (int j = 0; j < i; j++) {
                if (s.charAt(j) == '1') {
                    currentFlips++;
                }
            }
            // Flips for suffix s[i...n-1] to be all '1's
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == '0') {
                    currentFlips++;
                }
            }
            minFlips = Math.min(minFlips, currentFlips);
        }
        return minFlips;
    }
}
```
### Algorithm
*   Initialize `min_flips` to a very large number.
*   Get the length of the string, `n`.
*   Loop `i` from `0` to `n`. This `i` represents the split point where `0`s end and `1`s begin.
*   Inside the loop, initialize `current_flips = 0`.
*   Calculate flips for the prefix `s[0...i-1]` to become all `0`s. This is done by iterating from `j = 0` to `i-1` and counting the number of `'1'`s.
*   Calculate flips for the suffix `s[i...n-1]` to become all `1`s. This is done by iterating from `j = i` to `n-1` and counting the number of `'0'`s.
*   Update `min_flips = min(min_flips, current_flips)`.
*   After the outer loop finishes, `min_flips` will hold the minimum number of flips required.

## Prefix and Suffix Sums
This approach optimizes the brute-force method by avoiding redundant calculations. Instead of recounting the number of `1`s in the prefix and `0`s in the suffix for each split point, we can precompute these values. We use a prefix sum array to store the number of `1`s up to each index and a suffix sum array to store the number of `0`s from each index to the end.
**Time:** O(n) - The solution involves three separate passes over the string (or arrays of its size), each taking linear time. The overall complexity is O(n) + O(n) + O(n) = O(n). · **Space:** O(n) - We use two arrays, `prefixOnes` and `suffixZeros`, each of size `n+1`, to store the precomputed counts.
**Pros:** Efficient with a linear time complexity.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Uses extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
### Explanation
The cost for a split at index `i` is the sum of `(number of '1's in s[0...i-1])` and `(number of '0's in s[i...n-1])`. We can precompute these counts to make the calculation for each split point an O(1) operation.

First, we create a `prefixOnes` array. `prefixOnes[i]` stores the total count of `1`s in the substring `s[0...i-1]`. This array can be filled in a single pass from left to right.

Second, we create a `suffixZeros` array. `suffixZeros[i]` stores the total count of `0`s in the substring `s[i...n-1]`. This array is filled in a single pass from right to left.

Once both arrays are populated, we can iterate through all possible split points `i` from `0` to `n`. For each `i`, the total flips required is simply `prefixOnes[i] + suffixZeros[i]`. We find the minimum value among all these sums.

```java
class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[] prefixOnes = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i] + (s.charAt(i) == '1' ? 1 : 0);
        }

        int[] suffixZeros = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixZeros[i] = suffixZeros[i + 1] + (s.charAt(i) == '0' ? 1 : 0);
        }

        int minFlips = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            minFlips = Math.min(minFlips, prefixOnes[i] + suffixZeros[i]);
        }
        return minFlips;
    }
}
```
### Algorithm
*   Get the length of the string, `n`.
*   Create a `prefixOnes` array of size `n+1`. `prefixOnes[i]` will store the count of `1`s in `s[0...i-1]`.
*   Populate `prefixOnes` by iterating from left to right: `prefixOnes[i] = prefixOnes[i-1] + (s.charAt(i-1) == '1' ? 1 : 0)`.
*   Create a `suffixZeros` array of size `n+1`. `suffixZeros[i]` will store the count of `0`s in `s[i...n-1]`.
*   Populate `suffixZeros` by iterating from right to left: `suffixZeros[i] = suffixZeros[i+1] + (s.charAt(i) == '0' ? 1 : 0)`.
*   Initialize `min_flips` to a large value (e.g., `n`).
*   Iterate `i` from `0` to `n` (the split point).
*   For each `i`, the cost is `prefixOnes[i] + suffixZeros[i]`.
*   Update `min_flips = min(min_flips, cost)`.
*   Return `min_flips`.

## One-Pass Dynamic Programming
This is the most optimal approach, solving the problem in a single pass with constant extra space. It uses a dynamic programming-like logic. As we iterate through the string, we maintain a running count of the minimum flips required to make the prefix seen so far monotone.
**Time:** O(n) - We perform a single pass through the input string, making the time complexity linear with respect to the string's length. · **Space:** O(1) - We only use two integer variables (`flips` and `ones`), so the space usage is constant.
**Pros:** Optimal solution with O(n) time and O(1) space complexity.; Very concise and efficient implementation.
**Cons:** The logic, while concise, can be less intuitive to derive compared to the prefix sum approach.
### Explanation
We can solve this problem by iterating through the string just once. We maintain two key variables:

1.  `ones`: This counter keeps track of the number of `1`s we have encountered so far in the string.
2.  `flips`: This variable stores the minimum number of flips required to make the prefix of the string processed so far (`s[0...i]`) monotone increasing.

As we iterate through the string character by character:
*   If the character is a `'1'`, we simply increment the `ones` count. The current value of `flips` is still valid because we can append a `1` to an already monotone prefix without needing more flips.
*   If the character is a `'0'`, we face a choice. To make the current prefix `s[0...i]` monotone, we can either:
    a) Flip this `'0'` to a `'1'`. The cost for this is the minimum flips for the previous prefix (`s[0...i-1]`) plus one for the current flip. This is `flips + 1`.
    b) Keep this `'0'` as a `'0'`. For the prefix to remain monotone and end in `0`, it must be composed entirely of `0`s. This means we must flip all the `1`s we've seen so far. The cost for this is `ones`.

We should choose the option with the minimum cost. Therefore, we update `flips = Math.min(flips + 1, ones)`. After iterating through the entire string, the final value of `flips` is the minimum number of flips for the whole string.

```java
class Solution {
    public int minFlipsMonoIncr(String s) {
        int flips = 0;
        int ones = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                ones++;
            } else {
                // Option 1: Flip this '0' to '1'. Total flips = flips + 1.
                // Option 2: Keep this '0'. All previous '1's must be flipped. Total flips = ones.
                flips = Math.min(flips + 1, ones);
            }
        }
        return flips;
    }
}
```
### Algorithm
*   Initialize two integer variables, `flips = 0` and `ones = 0`.
*   Iterate through each character `c` of the input string `s`.
*   If `c` is `'1'`: 
    *   Increment the `ones` counter.
*   If `c` is `'0'`: 
    *   We have two choices to keep the prefix monotone: flip this `0` to `1` (cost: `flips + 1`) or keep it as `0` and flip all previous `1`s (cost: `ones`).
    *   Update `flips` to the minimum of these two options: `flips = min(flips + 1, ones)`.
*   After the loop completes, `flips` holds the minimum number of flips for the entire string to be monotone increasing.
*   Return `flips`.

# Solutions
### Java

```java
class Solution { public int minFlipsMonoIncr ( String s ) { int n = s . length (); int [] left = new int [ n + 1 ]; int [] right = new int [ n + 1 ]; int ans = Integer . MAX_VALUE ; for ( int i = 1 ; i <= n ; i ++) { left [ i ] = left [ i - 1 ] + ( s . charAt ( i - 1 ) == '1' ? 1 : 0 ); } for ( int i = n - 1 ; i >= 0 ; i --) { right [ i ] = right [ i + 1 ] + ( s . charAt ( i ) == '0' ? 1 : 0 ); } for ( int i = 0 ; i <= n ; i ++) { ans = Math . min ( ans , left [ i ] + right [ i ]); } return ans ; } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {number} */ var minFlipsMonoIncr = function (
  s,
) {
  const n = s.length;
  let presum = new Array(n + 1).fill(0);
  for (let i = 0; i < n; ++i) {
    presum[i + 1] = presum[i] + (s[i] == " 1 ");
  }
  let ans = presum[n];
  for (let i = 0; i < n; ++i) {
    ans = Math.min(ans, presum[i] + n - i - (presum[n] - presum[i]));
  }
  return ans;
};

```

### CPP

```cpp
class Solution { public: int minFlipsMonoIncr ( string s ) { int n = s . size (); vector < int > left ( n + 1 , 0 ), right ( n + 1 , 0 ); int ans = INT_MAX ; for ( int i = 1 ; i <= n ; ++ i ) { left [ i ] = left [ i - 1 ] + ( s [ i - 1 ] == '1' ); } for ( int i = n - 1 ; i >= 0 ; -- i ) { right [ i ] = right [ i + 1 ] + ( s [ i ] == '0' ); } for ( int i = 0 ; i <= n ; i ++ ) { ans = min ( ans , left [ i ] + right [ i ]); } return ans ; } };
```

### Python

```python
class Solution : def minFlipsMonoIncr ( self , s : str ) -> int : n = len ( s ) left , right = [ 0 ] * ( n + 1 ), [ 0 ] * ( n + 1 ) ans = 0x3F3F3F3F for i in range ( 1 , n + 1 ): left [ i ] = left [ i - 1 ] + ( 1 if s [ i - 1 ] == '1' else 0 ) for i in range ( n - 1 , - 1 , - 1 ): right [ i ] = right [ i + 1 ] + ( 1 if s [ i ] == '0' else 0 ) for i in range ( 0 , n + 1 ): ans = min ( ans , left [ i ] + right [ i ]) return ans
```