## Description

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.

Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.


Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.


Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.


Note:

1. 1 <= S.length <= 20000
2. S only consists of '0' and '1' characters.

## Solutions

### 1. Brute Force

# Time: O(n^2)
# Space: O(1)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
min_flips = float('inf')
for i in range(n):
cnt, cnt0, cnt1 = 0, 0, 0
for j in range(i):
if S[j] == '1':
cnt += 1
for l in range(i, n):
if S[l] == '0':
cnt += 1
for m in range(n):
if S[m] == '0':
cnt0 += 1
else:
cnt1 += 1
min_flips = min(min_flips, cnt, cnt0, cnt1)
return min_flips
# TLE


### 2. 1D-DP

从两端扫描。

# Time: O(n)
# Space: O(n)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
l = [0 for _ in range(n + 1)]
r = [0 for _ in range(n + 1)]
l = 1 if S == '1' else 0
r[n - 1] = 1 if S[n - 1] == '0' else 0

for i in range(1, n):
l[i] = l[i-1] + (1 if S[i] == '1' else 0)

for i in range(n-2, -1, -1):
r[i] = r[i+1] + (1 if S[i] == '0' else 0)

min_flips = r
for i in range(1, n + 1):
min_flips = min(min_flips, l[i - 1] + r[i])
return min_flips

# 81/81 cases passed (108 ms)
# Your runtime beats 15.62 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (14.3 MB)


### 2. 2D-DP

# Time: O(n)
# Sapce: O(n)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
dp = [[0 for _ in range(2)] for _ in range(n + 1)]
for i in range(1, n+1):
if S[i - 1] == '1':
dp[i] = dp[i-1] + 1
dp[i] = min(dp[i-1], dp[i-1])
else:
dp[i] = dp[i-1]
dp[i] = min(dp[i-1], dp[i - 1]) + 1
return min(dp[n], dp[n])
# 81/81 cases passed (144 ms)
# Your runtime beats 5.8 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (15.4 MB)


### 3. Optimized DP

当 dp[i] 只和 dp[i-1] 有关的话，可以进行降维！

# Time: O(n)
# Sapce: O(n)
class Solution:
def minFlipsMonoIncr(self, S: str) -> int:
if not S or len(S) == 0:
return 0
n = len(S)
dp0, dp1 = 0, 0
for i in range(1, n+1):
tmp0 = dp0 + (1 if S[i-1] == '1' else 0)
dp1 = min(dp0, dp1) + (1 if S[i-1] == '0' else 0)
dp0 = tmp0
return min(dp0, dp1)
# 81/81 cases passed (144 ms)
# Your runtime beats 5.8 % of python3 submissions
# Your memory usage beats 25 % of python3 submissions (15.4 MB)