926. Flip String to Monotone Increasing

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: String、Dynamic Programming

一、題目

A binary string is monotone increasing if it consists of some number of 0’s (possibly none), followed by some number of 1’s (also possibly none).
You are given a binary string s. You can flip s[i] changing 0 to 1 or from 1 to 0.
Return the minimum number of flips to make s monotone increasing.

Example 1:

  • Input: s = “00110”
  • Output: 1
  • Explanation: We flip the last digit to get 00111.

Example 2:

  • Input: s = “010110”
  • Output: 2
  • Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

  • Input: s = “00011000”
  • Output: 2
  • Explanation: We flip to get 00000000.

Constraints:

  • 1 <= s.length <= 10^5
  • s[i] is either '0' or '1'.

二、分析

  • 這題可以使用動態規劃來解題，將 dp[0][i] 訂為將 s[i] 翻成 0 可以符合題目需求的最少次數，dp[1][i] 為將 s[i] 翻成 1 可以符合題目需求的最少次數。
  • 當 s[i] == 0 時，前者一定要是 0；當 s[i] == 1 時，前者可以為 0 或 1。
  • 根據上述可以得到狀態轉移方程式為：
if (s[i] == '1') {
    dp[0][i] = dp[0][i-1] + 1;
    dp[1][i] = min(dp[0][i-1], dp[1][i-1]);
} else {
    dp[0][i] = dp[0][i-1];
    dp[1][i] = min(dp[0][i-1], dp[1][i-1]) + 1;
}

三、解題

1. DP

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int minFlipsMonoIncr(string s) {
    int n = s.length();
    vector<vector<int>> dp(2, vector<int>(n, 0));
    if (s[0] == '0') 
        dp[1][0] = 1;
    else
        dp[0][0] = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == '1') {
            dp[0][i] = dp[0][i-1] + 1;                  // 將 1 翻成 0
            dp[1][i] = min(dp[0][i-1], dp[1][i-1]);
        } else {
            dp[0][i] = dp[0][i-1];
            dp[1][i] = min(dp[0][i-1], dp[1][i-1]) + 1; // 將 0 翻成 1
        }
    }
    return min(dp[0][n-1], dp[1][n-1]);
}

1. DP(space optimized)

  • 從狀態轉移方程式觀察，可發現只與「前一狀態」相關，故可以進行狀態壓縮
  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int minFlipsMonoIncr(string s) {
    int n = s.length();
    int zero = 0;
    int one = 0;
    if (s[0] == '0') 
        one = 1;
    else
        zero = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == '1') {
            one = min(zero, one);
            zero++;
        } else {
            one = min(zero, one) + 1;
        }
    }
    return min(zero, one);
}

回目錄 Catalog