[926. flip the string to monotonic increment]

source ： Power button （LeetCode）

describe ：

If a binary string , With some 0（ There may be no 0） Followed by some 1（ Or maybe not 1） In the form of , Then the string is Monotone increasing Of .

Give you a binary string s, You can put any 0 Flip to 1 Or will 1 Flip to 0 .

Return to make s Monotonically increasing minimum number of flips .

Example 1：

 Input ：s = "00110"
 Output ：1
 explain ： Flip the last one to get  00111.

Example 2：

 Input ：s = "010110"
 Output ：2
 explain ： Flip to get  011111, Or is it  000111.

Example 3：

 Input ：s = "00011000"
 Output ：2
 explain ： Flip to get  00000000.

Tips ：

• 1 <= s.length <= 10⁵
• s[i] by ‘0’ or ‘1’

Method ： Dynamic programming

Code ：

class Solution {
    
public:
    int minFlipsMonoIncr(string &s) {
    
        int dp0 = 0, dp1 = 0;
        for (char c: s) {
    
            int dp0New = dp0, dp1New = min(dp0, dp1);
            if (c == '1') {
    
                dp0New++;
            } else {
    
                dp1New++;
            }
            dp0 = dp0New;
            dp1 = dp1New;
        }
        return min(dp0, dp1);
    }
};

Execution time ：16 ms, In all C++ Defeated in submission 96.07% Users of
Memory consumption ：10.8 MB, In all C++ Defeated in submission 73.81% Users of
Complexity analysis
Time complexity ： O(n), among n Is string s The length of . You need to traverse the string once , The time to calculate the minimum number of flips for each character is O(1).
Spatial complexity ： O(1). Using spatial optimization methods , The space complexity is O(1).
author：LeetCode-Solution