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

Example:

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.

public int minFlipsMonoIncr(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.

public int minFlipsMonoIncr(String s) {
  int n = s.length();
  // calculate prefix[] and suffix[]
  int[] prefix = new int[n];
  int[] suffix = new int[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]).

Consider a prefix s[0, i-1]: "001101" + "1" or "0"
a) if new 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) if new 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

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

public int minFlipsMonoIncr(String s) {
  int n = s.length();
  int[][] dp = new int[n][2];
  // init
  if (s.charAt(0) == '0') {
    dp[0][0] = 0;
    dp[0][1] = 1;
  } else {
    dp[0][0] = 1;
    dp[0][1] = 0;
  }
  for (int i = 1; i < n; ++i) {
    if (s.charAt(i) == '0') {
      dp[i][0] = dp[i - 1][0];
      dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
    } else { // == '1'
      dp[i][0] = dp[i - 1][0] + 1;
      dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
    }
  }
  return Math.min(dp[n - 1][0], dp[n - 1][1]);
}

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

Reduce Space Complexity to Constant Time:

public int minFlipsMonoIncr(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)$