# 926. Flip String to Monotone Increasing

Reference: LeetCode

Difficulty: Medium

My Post: Java Solutions with Full Explanations (B-F, DP x2, Constant Time & Space)

## Problem

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.

**Note:**

`1 <= s.length() <= 20000`

`s`

only consists of`'0'`

and`'1'`

characters.

**Example:**

1 | Input: "00000" |

**Follow up:** Reduce $O(N^2)$ to $O(N)$

## Analysis

### Brute-Force

In a brute-force fashion, We are going to consider all monotone increasing strings. For example, if the length is $4$, we consider `"1111", "0111", "0011", "0001" , "0000"`

. Specifically, we separate the array in zero-part `[0, k]`

and one-part in `[k+1, n-1]`

, where `-1 <= k <= n - 1`

.

1 | public int minFlipsMonoIncr(String s) { |

**Time:** $O(N^2)$**Space:** $O(1)$

Since `N`

could be 20000 at most, we cannot use $O(N^2)$ solution. Usually, if `N`

is greater than 5000, we cannot use $O(N^2)$ approach.

### DP (prefix + suffix)

In the counting part, we do a lot of repeated calculation. We denote:

`prefix[i]`

as the minimum number of flips (1 to 0) for prefix`s[0, i]`

, where`0 <= i <= n - 1`

.`suffix[i]`

as the minimum number of flips (0 to 1) for suffix`s[i, n - 1]`

, where`0 <= i <= n - 1`

.

1 | public int minFlipsMonoIncr(String s) { |

**Time:** $O(N)$**Space:** $O(N)$

### DP (Extra Dimension for States)

Define:

`dp[i][0]`

is the minimum number of flips for prefix`s[0, i]`

when`s[i]`

is required to be`0`

.`dp[i][1]`

is the minimum number of flips for prefix`s[0, i]`

when`s[i]`

is required to be`1`

.- Our goal is to calculate
`min(dp[n - 1][0], dp[n - 1][1])`

.

1 | Consider a prefix s[0, i-1]: "001101" + "1" or "0" |

Recurrence:

- If
`s[i]`

==`0`

:`dp[i][0]`

=`dp[i-1][0]`

`dp[i][1]`

= min(`dp[i-1][0]`

,`dp[i-1][1]`

) + 1

- Else
`s[i]`

==`1`

:`dp[i][0]`

=`dp[i-1][0]`

+ 1`dp[i][1]`

= min(`dp[i-1][0]`

,`dp[i-1][1]`

)

Initialization:

- If
`s[i]`

==`0`

:`dp[0][0]`

= 0`dp[0][1]`

= 1

- Else
`s[i]`

==`1`

:`dp[0][0]`

= 1`dp[0][1]`

= 0

1 | public int minFlipsMonoIncr(String s) { |

**Time:** $O(N)$**Space:** $O(N)$

**Reduce Space Complexity to Constant Time:**

1 | public int minFlipsMonoIncr(String s) { |

**Time:** $O(N)$**Space:** $O(1)$