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 2 3 4 5 6 7 8 9 10 11

Input: "00000" Output: 0

Input: "00110" Output: 1

Input: "010110" Output: 2

Input: "00011000" Output: 2

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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

publicintminFlipsMonoIncr(String s) { intn= s.length(); intminCount= Integer.MAX_VALUE; for (intk= -1; k <= n - 1; ++k) { // k is ranging from [-1, n-1] intcount=0; // zero-part for (inti=0; i <= k; ++i) { if (s.charAt(i) == '1') ++count; } // one-part for (inti= k + 1; i <= n - 1; ++i) { if (s.charAt(i) == '0') ++count; } minCount = Math.min(minCount, count); } return minCount; }

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.

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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Consider a prefix s[0, i-1]: "001101" + "1" or "0" a) ifnewvalue is s[i] == 0 - dp[i][0] = dp[i-1][0] - newvalue is 0, s[i] is required to be 0, - thus do not flip the newvalue - dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1 - newvalue is 0, s[i] is required to be 1, - thus flip the newvalue from 0 to 1 - notice whether the last second is 1 or 0 is okay b) ifnewvalue is s[i] == 1 - dp[i][0] = dp[i-1][0] + 1 - newvalue is 1, s[i] is required to be 0, - thus flip the newvalue from 1 to 0 - notice the last second must be 0 (or it is illegal) - dp[i][1] = min(dp[i-1][0], dp[i-1][1]) - newvalue is 1, s[i] is required to be 1, - thus do not flip the newvalue

publicintminFlipsMonoIncr(String s) { intn= s.length(); int f0, f1; // init if (s.charAt(0) == '0') f0 = 0; f1 = 1; else f0 = 1; f1 = 0; // dp for (inti=1; i < n; ++i) { if (s.charAt(i) == '0') { // int minTemp = Math.min(f0, f1); f0 = f0; f1 = Math.min(f0, f1) + 1; // actually do not need minTemp } else { // == '1' intminTemp= Math.min(f0, f1); f0 = f0 + 1; f1 = minTemp; // or calculate the f1 first then get rid of minTemp } } return Math.min(f0, f1); }