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){ int n = s.length(); int minCount = Integer.MAX_VALUE; for (int k = -1; k <= n - 1; ++k) { // k is ranging from [-1, n-1] int count = 0; // zero-part for (int i = 0; i <= k; ++i) { if (s.charAt(i) == '1') ++count; } // one-part for (int i = 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.

publicintminFlipsMonoIncr(String s){ int n = s.length(); // calculate prefix[] and suffix[] int[] prefix = newint[n]; int[] suffix = newint[n]; prefix[0] = s.charAt(0) == '1' ? 1 : 0; suffix[n - 1] = s.charAt(n - 1) == '0' ? 1 : 0; for (int i = 1, j = n - 2; i < n; ++i, --j) { prefix[i] = prefix[i - 1] + (s.charAt(i) == '1' ? 1 : 0); suffix[j] = suffix[j + 1] + (s.charAt(j) == '0' ? 1 : 0); } // calculate the count int minCount = Integer.MAX_VALUE; for (int k = -1; k <= n - 1; ++k) { // 0: [0, k], 1: [k+1, n-1] int left = (k == -1) ? 0 : prefix[k]; int right = (k + 1 == n) ? 0 : suffix[k + 1]; minCount = Math.min(minCount, left + right); } return minCount; }

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 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) ifnew value is s[i] == 0 - dp[i][0] = dp[i-1][0] - new value is 0, s[i] is required to be 0, - thus do not flip the new value - dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1 - new value is 0, s[i] is required to be 1, - thus flip the new value from 0 to 1 - notice whether the last second is 1 or 0 is okay b) ifnew value is s[i] == 1 - dp[i][0] = dp[i-1][0] + 1 - new value is 1, s[i] is required to be 0, - thus flip the new value 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]) - new value is 1, s[i] is required to be 1, - thus do not flip the new value

publicintminFlipsMonoIncr(String s){ int n = s.length(); int f0, f1; // init if (s.charAt(0) == '0') f0 = 0; f1 = 1; else f0 = 1; f1 = 0; // dp for (int i = 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' int minTemp = Math.min(f0, f1); f0 = f0 + 1; f1 = minTemp; // or calculate the f1 first then get rid of minTemp } } return Math.min(f0, f1); }

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

Comment

Junhao Wang

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