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 <= S.length <= 20000
S only consists of '0' and '1' characters.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def minFlipsMonoIncr(self, S: str) -> int:
        

Solutions:
class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		onesSoFar = 0
		partial = 0
		for n in S:
			if n == '0':
				partial = min(onesSoFar, partial + 1)
			else:
				onesSoFar += 1
		return partial


class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		if not S:
			return 0
		n = len(S)
		if n == 1:
			return 0
		total_1s = 0
		total_0s = 0
		for char in S:
			if char == '1':
				total_1s += 1
			else:
				total_0s += 1
		if total_1s == 0 or total_0s == 0:
			return 0
		prefix_sum = 0
		ans = float('inf')
		for i in range(n):
			prefix_sum += 1 if S[i] == '1' else 0
			ans = min(ans, prefix_sum + (n - i - 1 - (total_1s - prefix_sum)))
		return min(ans, total_0s, total_1s)


class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		at0 = 0
		at1 = 0
		num0 = 0
		for a in S:
			if a == '0':
				at1 = min(at1, at0) + 1
			else:
				at1 = min(at1, at0)
				at0 += 1
		return min(at1, at0)


class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		str_len = len(S)
		count_arr = [[0, 0] for x in range(str_len)]
		one_start_idx = -1
		for i in range(len(S)):
			if S[i] == '0':
				if i == 0:
					count_arr[i][0] += 1
					count_arr[i][1] = 0
				else:
					count_arr[i][0] = count_arr[i - 1][0] + 1
					count_arr[i][1] = count_arr[i - 1][1]
			else:
				if i == 0:
					count_arr[i][1] += 1
				else:
					count_arr[i][1] = count_arr[i - 1][1] + 1
					count_arr[i][0] = count_arr[i - 1][0]
				if one_start_idx == -1:
					one_start_idx = i
		total_flips = []
		total_flips.append(min(count_arr[str_len - 1][0], count_arr[str_len - 1][1]))
		for i in range(one_start_idx, str_len):
			if i == 0:
				total_flips.append(count_arr[str_len - 1][0] - count_arr[i][0])
			elif i == str_len - 1:
				total_flips.append(count_arr[str_len - 1][0])
			else:
				total_flips.append(count_arr[i - 1][1] + count_arr[str_len - 1][0] - count_arr[i][0])
		return min(total_flips)


class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		dp = 0
		ones = 0
		for c in S:
			if c == '0':
				dp = min(1 + dp, ones)
			else:
				dp = min(dp, 1 + ones)
				ones += 1
		return dp


class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		(flip, one) = (0, 0)
		for i in S:
			if i == '1':
				one += 1
			else:
				flip += 1
			flip = min(one, flip)
		return flip


class Solution:

	def minFlipsMonoIncr(self, S: str) -> int:
		(n, prefix, total, res) = (len(S), 0, S.count('1'), sys.maxsize)
		for i in range(n + 1):
			res = min(res, prefix + len(S) - i - total + prefix)
			if i < n:
				prefix += 1 if S[i] == '1' else 0
		return res