926. Flip String to Monotone Increasing Time: $O(|\texttt{s}|)$ Space: $O(1)$ C++JavaPython 1 2 3 4 5 6 7 8 9 10 11 12 13 14class Solution { public: int minFlipsMonoIncr(string s) { vector<int> dp(2); for (const char c : s) { const int temp = dp[0] + (c == '1'); dp[1] = min(dp[0], dp[1]) + (c == '0'); dp[0] = temp; } return min(dp[0], dp[1]); } }; 1 2 3 4 5 6 7 8 9 10 11 12 13class Solution { public int minFlipsMonoIncr(String s) { int[] dp = new int[2]; for (final char c : s.toCharArray()) { final int temp = dp[0] + (c == '1' ? 1 : 0); dp[1] = Math.min(dp[0], dp[1]) + (c == '0' ? 1 : 0); dp[0] = temp; } return Math.min(dp[0], dp[1]); } } 1 2 3 4 5 6 7 8class Solution: def minFlipsMonoIncr(self, s: str) -> int: dp = [0] * 2 for c in s: dp[0], dp[1] = dp[0] + (c == '1'), min(dp[0], dp[1]) + (c == '0') return min(dp)