Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.
Example 1:
Input:
S = "001"
Output: 1
Explanation: 
We can flip the 0th bit to 1 to have
101.
Example 2:
Input:
S = "0001010111" 
Output: 2
Explanation: We can flip the 1st and 8th bit 
bit to have "0101010101"
101.
Your Task:
You don't need to read input or print anything. Your task is to complete the function minFlips() which takes the string S as input and returns the minimum number of flips required.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Bit manipulation

Data structures

Starter code: #User function Template for python3





class Solution:

    def minFlips(self, S):

        # Code here

        



Solutions:
class Solution:

	def minFlips(self, S):
		ans1 = 0
		j = 0
		for i in S:
			if j % 2 == 0:
				if i == '0':
					ans1 += 1
			elif i == '1':
				ans1 += 1
			j += 1
		ans2 = 0
		j = 1
		for i in S:
			if j % 2 == 0:
				if i == '0':
					ans2 += 1
			elif i == '1':
				ans2 += 1
			j += 1
		return min(ans1, ans2)


class Solution:

	def minFlips(self, s):
		return min(self.find(s, 0), self.find(s, 1))

	def find(self, s, expected):
		total = 0
		for x in range(len(s)):
			if int(s[x]) != expected:
				total += 1
			expected = not expected
		return total


class Solution:

	def minFlips(self, S):
		ans = 0
		fword = '0'
		for i in range(len(S)):
			if S[i] == fword:
				ans += 1
				fword = str(1 - int(S[i]))
			else:
				fword = S[i]
		ans1 = 0
		fword = '1'
		for i in range(len(S)):
			if S[i] == fword:
				ans1 += 1
				fword = str(1 - int(S[i]))
			else:
				fword = S[i]
		return min(ans, ans1)


class Solution:

	def minFlips(self, S):
		rcount = 0
		lcount = 0
		for i in range(len(S)):
			if i % 2 == 0 and S[i] != '1':
				rcount += 1
			elif i % 2 != 0 and S[i] != '0':
				rcount += 1
		for i in range(len(S)):
			if i % 2 == 0 and S[i] != '0':
				lcount += 1
			elif i % 2 != 0 and S[i] != '1':
				lcount += 1
		return min(lcount, rcount)


class Solution:

	def minFlips(self, s):
		count = 0
		for i in range(len(s)):
			if i % 2 == 0:
				if s[i] != '1':
					count += 1
			elif s[i] != '0':
				count += 1
		return min(count, len(s) - count)


class Solution:

	def flip(self, temp):
		return '0' if temp == '1' else '1'

	def flipCount(self, s, ch):
		count = 0
		for i in range(len(s)):
			if s[i] != ch:
				count = count + 1
			ch = self.flip(ch)
		return count

	def minFlips(self, s):
		return min(self.flipCount(s, '0'), self.flipCount(s, '1'))


class Solution:

	def minFlips(self, S):
		d1 = 0
		d2 = 0
		for i in range(len(S)):
			if i % 2:
				f = int(S[i]) ^ 0
			else:
				f = int(S[i]) ^ 1
			if f == 1:
				d1 += 1
		for i in range(len(S)):
			if i % 2 == 0:
				f = int(S[i]) ^ 0
			else:
				f = int(S[i]) ^ 1
			if f == 1:
				d2 += 1
		return min(d1, d2)


class Solution:

	def minFlips(self, s):
		c = 0
		l = list(s)
		n = len(l)
		for i in range(n):
			if i % 2 == 0:
				if l[i] == '1':
					c += 1
			if i % 2 != 0:
				if l[i] == '0':
					c += 1
		x = n - c
		ans = min(x, c)
		return ans


class Solution:

	def minFlips(self, S):

		def flipCount(s, expected):
			flipcnt = 0
			for i in s:
				if i != expected:
					flipcnt += 1
				if expected == '1':
					expected = '0'
				else:
					expected = '1'
			return flipcnt
		return min(flipCount(S, '0'), flipCount(S, '1'))


class Solution:

	def minFlips(self, S):
		ans1 = 0
		for (idx, num) in enumerate(S):
			if idx % 2 == 0 and num == '1':
				ans1 += 1
			elif idx % 2 != 0 and num == '0':
				ans1 += 1
		ans2 = 0
		for (idx, num) in enumerate(S):
			if idx % 2 == 0 and num == '0':
				ans2 += 1
			elif idx % 2 != 0 and num == '1':
				ans2 += 1
		return min(ans1, ans2)


class Solution:

	def minFlips(self, S):
		flip = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					flip += 1
			if i % 2 != 0:
				if S[i] == '1':
					flip += 1
		c = min(flip, len(S) - flip)
		return c


class Solution:

	def minFlips(self, S):
		n = len(S)
		count_with_0 = 0
		for i in range(n):
			if i % 2 == 0 and S[i] == '1':
				count_with_0 += 1
			elif i % 2 == 1 and S[i] == '0':
				count_with_0 += 1
		count_with_1 = 0
		for i in range(n):
			if i % 2 == 0 and S[i] == '0':
				count_with_1 += 1
			elif i % 2 == 1 and S[i] == '1':
				count_with_1 += 1
		return min(count_with_0, count_with_1)


class Solution:

	def minFlips(self, S):
		count_if_0 = 0
		count_if_1 = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '1':
					count_if_0 += 1
				else:
					count_if_1 += 1
			elif S[i] == '0':
				count_if_0 += 1
			else:
				count_if_1 += 1
		return min(count_if_0, count_if_1)


class Solution:

	def minFlips(self, S):
		n = len(S)
		(f1, f2) = (0, 0)
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					pass
				else:
					f1 += 1
			elif S[i] == '1':
				pass
			else:
				f1 += 1
			if i % 2 == 0:
				if S[i] == '1':
					pass
				else:
					f2 += 1
			elif S[i] == '0':
				pass
			else:
				f2 += 1
		return min(f1, f2)


class Solution:

	def minFlips(self, S):
		dp = [[0, 0] for i in range(len(S))]
		if S[0] == '0':
			dp[0][1] = 1
		else:
			dp[0][0] = 1
		for i in range(1, len(S)):
			if S[i] == '1':
				dp[i][1] = dp[i - 1][0]
				dp[i][0] = dp[i - 1][1] + 1
			else:
				dp[i][1] = dp[i - 1][0] + 1
				dp[i][0] = dp[i - 1][1]
		return min(dp[-1])


class Solution:

	def minFlips(self, string):
		flips1 = 0
		flips2 = 0
		for i in range(len(string)):
			if i % 2 == 0:
				if string[i] == '1':
					flips1 += 1
				else:
					flips2 += 1
			elif string[i] == '0':
				flips1 += 1
			else:
				flips2 += 1
		return min(flips1, flips2)


class Solution:

	def minFlips(self, s):
		f = 0
		for i in range(len(s)):
			if i % 2 == 0:
				if s[i] == '0':
					f += 1
			if i % 2 != 0:
				if s[i] == '1':
					f += 1
		c = min(f, len(s) - f)
		return c


class Solution:

	def minFlips(self, S):
		A = list(map(int, S))
		(s1, s2) = (0, 0)
		for i in range(len(A)):
			if i % 2 == 0 and A[i] != 0:
				s1 += 1
			if i % 2 == 0 and A[i] != 1:
				s2 += 1
			if i % 2 != 0 and A[i] != 1:
				s1 += 1
			if i % 2 != 0 and A[i] != 0:
				s2 += 1
		return min(s1, s2)


class Solution:

	def minFlips(self, S):
		v0 = 0
		v1 = 0
		for i in range(len(S)):
			if i % 2 == 0 and S[i] == '0':
				v0 += 1
			elif i % 2 == 1 and S[i] == '1':
				v0 += 1
			if i % 2 != 0 and S[i] == '0':
				v1 += 1
			elif i % 2 != 1 and S[i] == '1':
				v1 += 1
		return min(v1, v0)


class Solution:

	def minFlips(self, S):
		res = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					res += 1
			elif S[i] == '1':
				res += 1
		return min(res, len(S) - res)


class Solution:

	def minFlips(self, S):

		def flip(ch):
			return '1' if ch == '0' else '0'

		def getFlipWith(S, expected):
			flipCount = 0
			for i in range(len(S)):
				if S[i] != expected:
					flipCount += 1
				expected = flip(expected)
			return flipCount
		return min(getFlipWith(S, '0'), getFlipWith(S, '1'))


def f(prev, str):
	res = 0
	for i in range(len(str)):
		if prev == 0 and str[i] == '0' or (prev == 1 and str[i] == '1'):
			res += 1
		prev = 1 - prev
	return res

class Solution:

	def minFlips(self, S):
		return min(f(0, S), f(1, S))


def function(prev, str):
	count = 0
	for i in range(len(str)):
		if prev == 0 and str[i] == '0' or (prev == 1 and str[i] == '1'):
			count = count + 1
		prev = 1 - prev
	return count

class Solution:

	def minFlips(self, S):
		return min(function(0, S), function(1, S))


class Solution:

	def minFlips(self, S):
		even_zeros = 0
		odd_zeros = 0
		even_ones = 0
		odd_ones = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					even_zeros += 1
				else:
					even_ones += 1
			elif S[i] == '0':
				odd_zeros += 1
			else:
				odd_ones += 1
		result = min(even_zeros + odd_ones, even_ones + odd_zeros)
		return result


class Solution:

	def minFlips(self, S):
		(c1, c2, k1, k2, r) = (0, 0, 1, 0, True)
		for i in S:
			if int(i) != k1:
				c1 += 1
			if int(i) != k2:
				c2 += 1
			if r == True:
				k1 = 0
				k2 = 1
			else:
				k1 = 1
				k2 = 0
			r = not r
		return min(c1, c2)


class Solution:

	def minFlips(self, string):
		count_0 = 0
		count_1 = 0
		for i in range(len(string)):
			if i % 2 == 0 and string[i] != '0':
				count_0 += 1
			elif i % 2 == 1 and string[i] != '1':
				count_0 += 1
			if i % 2 == 0 and string[i] != '1':
				count_1 += 1
			elif i % 2 == 1 and string[i] != '0':
				count_1 += 1
		return min(count_0, count_1)


class Solution:

	def minFlips(self, str1):
		str2 = str1 + str1
		temp1 = ''
		temp2 = ''
		l = len(str1)
		for i in range(0, l):
			temp1 += '01'
		for i in range(0, l):
			temp2 += '10'
		res1 = 0
		res2 = 0
		for i in range(0, l):
			if str1[i] != temp1[i]:
				res1 += 1
			if str1[i] != temp2[i]:
				res2 += 1
			if i >= l:
				if str1[i] != temp1[i]:
					res1 -= 1
				if str1[i] != temp2[i]:
					res2 -= 1
		return min(res1, res2)


class Solution:

	def minFlips(self, s):
		change = 0
		even_1 = 0
		even_0 = 0
		odd_1 = 0
		odd_0 = 0
		for i in range(len(s)):
			if i % 2 == 0:
				if s[i] == '1':
					even_1 += 1
				else:
					even_0 += 1
			elif s[i] == '1':
				odd_1 += 1
			else:
				odd_0 += 1
		if even_1 + odd_0 > even_0 + odd_1:
			change = even_0 + odd_1
		else:
			change = even_1 + odd_0
		return change


class Solution:

	def minFlips(self, s):
		c1 = 0
		c2 = 0
		ele = '0'
		n = len(s)
		for i in range(0, n):
			if s[i] != ele:
				c1 = c1 + 1
			else:
				c2 = c2 + 1
			if ele == '0':
				ele = '1'
			else:
				ele = '0'
		return min(c1, c2)


class Solution:

	def minFlips(self, S):
		L = list(map(int, S))
		x1 = 0
		x2 = 0
		for i in range(len(L)):
			if i % 2 == 0 and L[i] != 0:
				x1 += 1
			if i % 2 == 0 and L[i] != 1:
				x2 += 1
			if i % 2 != 0 and L[i] != 1:
				x1 += 1
			if i % 2 != 0 and L[i] != 0:
				x2 += 1
		return min(x1, x2)


class Solution:

	def minFlips(self, S):
		one = 0
		zero = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					one += 1
				else:
					zero += 1
			elif S[i] == '0':
				zero += 1
			else:
				one += 1
		return min(one, zero)


class Solution:

	def minFlips(self, S):
		n = len(S)
		flips_0 = 0
		flips_1 = 0
		for i in range(n):
			if i % 2 == 0 and S[i] == '1':
				flips_0 += 1
			elif i % 2 == 1 and S[i] == '0':
				flips_0 += 1
			if i % 2 == 0 and S[i] == '0':
				flips_1 += 1
			elif i % 2 == 1 and S[i] == '1':
				flips_1 += 1
		return min(flips_0, flips_1)


class Solution:

	def minFlips(self, S):
		t = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					t += 1
			elif S[i] == '1':
				t += 1
		c = min(t, len(S) - t)
		return c
		e


class Solution:

	def minFlips(self, S):
		c = 0
		b = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '0':
					c += 1
				else:
					b += 1
			elif S[i] == '0':
				b += 1
			else:
				c += 1
		return min(c, b)


class Solution:

	def minFlips(self, s):
		c = 0
		for i in range(len(s)):
			if i % 2 == 0 and s[i] != '1':
				c += 1
			elif i % 2 == 1 and s[i] != '0':
				c += 1
		c1 = 0
		for i in range(len(s)):
			if i % 2 == 0 and s[i] != '0':
				c1 += 1
			elif i % 2 == 1 and s[i] != '1':
				c1 += 1
		return min(c, c1)


class Solution:

	def minFlips(self, S):
		n = len(S)
		(a, b) = (0, 0)
		for i in range(n):
			if i % 2 != 0 and S[i] == '0':
				a += 1
			elif i % 2 == 0 and S[i] == '1':
				a += 1
			elif i % 2 != 0 and S[i] == '1':
				b += 1
			elif i % 2 == 0 and S[i] == '0':
				b += 1
		return min(a, b)


class Solution:

	def minFlips(self, S):
		(c1, c2) = (0, 0)
		for i in range(len(S)):
			if i & 1 == 0 and S[i] == '0':
				c1 += 1
			if i & 1 == 1 and S[i] == '1':
				c1 += 1
			if i & 1 == 0 and S[i] == '1':
				c2 += 1
			if i & 1 == 1 and S[i] == '0':
				c2 += 1
		return min(c1, c2)


class Solution:

	def minFlips(self, S):
		n = len(S)
		s1 = '10' * n
		s2 = '01' * n
		(c1, c2) = (0, 0)
		i = 0
		while i < n:
			if S[i] != s1[i]:
				c1 += 1
			if S[i] != s2[i]:
				c2 += 1
			i += 1
		return min(c1, c2)


class Solution:

	def minFlips(self, S):
		n = len(S)
		one = ['1']
		zero = ['0']
		trigger = False
		for i in range(1, n):
			if i % 2 == 0:
				one.append('1')
				zero.append('0')
			else:
				one.append('0')
				zero.append('1')
		one = ''.join(one)
		zero = ''.join(zero)
		zerocount = 0
		onecount = 0
		for i in range(n):
			if S[i] != zero[i]:
				zerocount += 1
			if S[i] != one[i]:
				onecount += 1
		return min(zerocount, onecount)


class Solution:

	def minFlips(self, string):
		temp1 = 1
		temp0 = 0
		flip0 = 0
		flip1 = 0
		for character in string:
			if character != str(temp1):
				flip1 += 1
			if character != str(temp0):
				flip0 += 1
			temp0 = int(not temp0)
			temp1 = int(not temp1)
		return min(flip0, flip1)


class Solution:

	def minFlips(self, S):
		s = list(S)
		X = ''
		cs = 0
		cx = 0
		for i in S:
			X += i
		x = list(X)
		for i in range(len(S)):
			if i % 2 != 0 and s[i] == '0':
				s[i] = '1'
				cs += 1
			elif i % 2 == 0 and s[i] == '1':
				s[i] = '0'
				cs += 1
		for j in range(len(X)):
			if j % 2 != 0 and x[j] == '1':
				x[j] = '0'
				cx += 1
			elif j % 2 == 0 and x[j] == '0':
				x[j] = '1'
				cx += 1
		return min(cs, cx)


class Solution:

	def minFlips(self, S):
		n = len(S)
		count = 0
		for i in range(0, n, 2):
			if S[i] == '0':
				count += 1
		for i in range(1, n, 2):
			if S[i] == '1':
				count += 1
		return min(count, n - count)


class Solution:

	def minFlips(self, S):
		(toggle, cnt1) = (1, 0)
		for c in S:
			if toggle and c != '1':
				cnt1 += 1
			elif not toggle and c != '0':
				cnt1 += 1
			toggle = 1 - toggle
		(toggle, cnt2) = (0, 0)
		for c in S:
			if toggle and c != '1':
				cnt2 += 1
			elif not toggle and c != '0':
				cnt2 += 1
			toggle = 1 - toggle
		return min(cnt1, cnt2)


class Solution:

	def minFlips(self, S):

		def flip(ch):
			return '0' if ch == '1' else '1'

		def countflips(S, expect):
			flipcount = 0
			for i in range(len(S)):
				if S[i] != expect:
					flipcount += 1
				expect = flip(expect)
			return flipcount
		return min(countflips(S, '0'), countflips(S, '1'))


class Solution:

	def minFlips(self, S):
		count1 = 0
		count2 = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] == '1':
					count1 += 1
				else:
					count2 += 1
			elif S[i] == '0':
				count1 += 1
			else:
				count2 += 1
		return min(count1, count2)


class Solution:

	def minFlips(self, s):
		x = len(s) // 2
		y = '01' * x
		z = '10' * x
		if len(s) % 2 != 0:
			y += '0'
			z += '1'
		yy = 0
		zz = 0
		for i in range(len(s)):
			if y[i] != s[i]:
				yy += 1
			if z[i] != s[i]:
				zz += 1
		return min(yy, zz)


class Solution:

	def minFlips(self, S):
		N = len(S)
		flips = 0
		for i in range(N):
			if i & 1 == 0:
				if S[i] == '0':
					flips += 1
			elif S[i] == '1':
				flips += 1
		temp = N - flips
		ans = min(flips, temp)
		return ans


class Solution:

	def minFlips(self, s):
		p1 = 0
		p2 = 0
		for i in range(len(s)):
			if s[i] == '1':
				if i % 2 == 0:
					p1 += 1
				else:
					p2 += 1
		b = len(s) // 2
		a = len(s) // 2
		if len(s) % 2:
			a += 1
		c1 = a - p1
		c2 = b - p2
		p = max(p1, c1)
		q = max(p2, c2)
		if p > q:
			if p1 > c1:
				return c1 + p2
			else:
				return p1 + c2
		elif p2 > c2:
			return c2 + p1
		else:
			return p2 + c1


class Solution:

	def minFlips(self, S):
		n = len(S)
		odd = S[1::2]
		even = S[::2]
		first = odd.count('1') + even.count('0')
		second = odd.count('0') + even.count('1')
		return n - max(first, second)


class Solution:

	def minFlips(self, S):
		ans1 = 0
		exp = '0'
		for i in range(len(S)):
			if exp != S[i]:
				ans1 += 1
			if exp == '0':
				exp = '1'
			else:
				exp = '0'
		ans2 = 0
		exp = '1'
		for i in range(len(S)):
			if exp != S[i]:
				ans2 += 1
			if exp == '0':
				exp = '1'
			else:
				exp = '0'
		return min(ans1, ans2)


import math

class Solution:

	def minFlips(self, S):
		mini = math.inf
		(count, count1) = (0, 0)
		n = len(S)
		for i in range(n):
			if i % 2 == 0 and int(S[i]) ^ 0 != 0:
				count += 1
			elif i % 2 != 0 and int(S[i]) ^ 1 != 0:
				count += 1
		for i in range(n):
			if i % 2 == 0 and int(S[i]) ^ 1 != 0:
				count1 += 1
			elif i % 2 != 0 and int(S[i]) ^ 0 != 0:
				count1 += 1
		return min(count, count1)


class Solution:

	def minFlips(self, S):
		firstTry = '0'
		flips1 = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] != firstTry:
					flips1 += 1
				firstTry = '1'
			else:
				if S[i] != firstTry:
					flips1 += 1
				firstTry = '0'
		secondTry = '1'
		flips2 = 0
		for i in range(len(S)):
			if i % 2 == 0:
				if S[i] != secondTry:
					flips2 += 1
				secondTry = '0'
			else:
				if S[i] != secondTry:
					flips2 += 1
				secondTry = '1'
		flips = min(flips1, flips2)
		return flips


class Solution:

	def minFlips(self, S):
		S = list(S)
		minCount = min(self.getMinValue(S, '0'), self.getMinValue(S, '1'))
		return minCount

	def getMinValue(self, S, expected):
		flipCount = 0
		for i in range(len(S)):
			if S[i] != expected:
				flipCount += 1
			expected = self.flip(expected)
		return flipCount

	def flip(self, value):
		if value == '1':
			return '0'
		return '1'


class Solution:

	def minFlips(self, S):
		flip = 0
		for i in range(len(S)):
			if i & 1:
				if S[i] == '0':
					flip += 1
			elif S[i] == '1':
				flip += 1
		t = len(S) - flip
		ans = min(t, flip)
		return ans


class Solution:

	def minFlips(self, S):

		def even(x):
			count = 0
			for i in range(len(S)):
				if i % 2 == 0 and S[i] != x:
					count = count + 1
				if i % 2 != 0 and S[i] == x:
					count = count + 1
			return count
		return min(even('1'), even('0'))


class Solution:

	def minFlips(self, S):
		n = len(S)

		def count(start):
			r = 0
			curr = start
			for i in range(n):
				if S[i] != str(curr):
					r += 1
				curr = 1 if curr == 0 else 0
			return r
		return min(count(0), count(1))


class Solution:

	def minFlips(self, S):

		def flip(ch):
			return '0' if ch == '1' else '1'

		def getFlipWithStartingCharacter(string, expected):
			count = 0
			for i in range(len(string)):
				if string[i] != expected:
					count += 1
				expected = flip(expected)
			return count
		return min(getFlipWithStartingCharacter(S, '0'), getFlipWithStartingCharacter(S, '1'))


class Solution:

	def minFlips(self, S):
		s = list(S)
		n = len(s)
		count_i = 0
		count_j = 0
		expected = '0'
		for i in range(n):
			if s[i] != expected:
				count_i += 1
			if expected == '0':
				expected = '1'
			else:
				expected = '0'
		expected = '1'
		for i in range(n):
			if s[i] != expected:
				count_j += 1
			if expected == '0':
				expected = '1'
			else:
				expected = '0'
		return min(count_i, count_j)


class Solution:

	def minFlips(self, s):
		return min(self.flips(s, 0), self.flips(s, 1))

	def flips(self, s, k):
		(ans, i) = (0, 0)
		while i < len(s):
			if int(s[i]) != k:
				ans += 1
			i += 2
		j = 1
		k ^= 1
		while j < len(s):
			if int(s[j]) != k:
				ans += 1
			j += 2
		return ans