Reference: LeetCode
Difficulty: Medium

## 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. 1 <= s.length() <= 20000
2. s only consists of '0' and '1' characters.

Example:

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.

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.

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]).

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

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

Reduce Space Complexity to Constant Time:

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.