LeetCode 926 Flip String to Monotone Increasing

LeetCode

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 it from 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<sup>5</sup> s[i] is either '0' or '1'.

题目大意：

01字符串中Flip其中一些将它变成00111,0和1的个数是任意。

DP解题思路(推荐)：

求最小值考虑用BFS或者DP。BFS的复杂度可能比较大，DP定义为以s[i]为结尾的最小flip数，但由于不知道具体排列(末状态)是什么或者结尾是什么，所以比较难从子问题推导出来。
不妨用两个dp来计算，
dp为以0为结尾的最小flip数
dp2为以1为结尾的最小flip数

dp = dp     if s[i] = '0'
   = dp + 1 if s[i] = '1'
   
dp2 = min(dp2 + 1, dp + 1)     if s[i] = '0'
    = min(dp2, dp)             if s[i] = '1'

公式不是对称，因为题意是先0再1。

解题步骤：

N/A

注意事项：

1. 用Python的dp和dp2同时由前状态赋值，这样避免用临时变量

Python代码：

def minFlipsMonoIncr(self, s: str) -> int:
	dp, dp2 = 0, 0
	for i in range(len(s)):
		if s[i] == '0':
			dp, dp2 = dp, min(dp, dp2) + 1
		else:
			dp, dp2 = dp + 1, min(dp2, dp)
	return min(dp, dp2)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

---

presum算法II解题思路：

统计1的个数，若是0同时统计从0 flip到1的个数，取两者较小为新flip数。较难理解，不推荐

Python代码：

def minFlipsMonoIncr2(self, s: str) -> int:
	ones, flips = 0, 0
	for c in s:
		if c == '1':
			ones += 1
		else:
			flips += 1
		flips = min(ones, flips)
	return flips

算法分析：

时间复杂度为O(n)，空间复杂度O(1)