Alice has a binary string. She thinks a binary string is beautiful if and only if it doesn't contain the substring $\text{"010"}$. 

In one step, Alice can change a $0$ to a $1$ or vice versa. Count and print the minimum number of steps needed to make Alice see the string as beautiful.

Example    

$b=\textbf{010}$    

She can change any one element and have a beautiful string.

Function Description  

Complete the beautifulBinaryString function in the editor below.   

beautifulBinaryString has the following parameter(s):  

string b: a string of binary digits   

Returns   

int: the minimum moves required

Input Format

The first line contains an integer $n$, the length of binary string. 

The second line contains a single binary string $\boldsymbol{b}$.

Constraints

$1\leq n\leq100$
$b[i]\in\{0,1\}$.

Output Format

Print the minimum number of steps needed to make the string beautiful.

Sample Input 0

STDIN       Function
-----       --------
7           length of string n = 7
0101010     b = '0101010'

Sample Output 0

2  

Explanation 0: 

In this sample, $b=\text{"0101010"}$

The figure below shows a way to get rid of each instance of $\text{"010"}$:

Make the string beautiful by changing $2$ characters ($b[2]$ and $b\left[5\right]$).

Sample Input 1

5
01100

Sample Output 1

0

Sample Case 1:

In this sample $b=\text{"01100"}$     

Explanation 1

The substring $\text{"010"}$ does not occur in $\boldsymbol{b}$, so the string is already beautiful in $0$ moves.

Sample Input 2

10
0100101010

Sample Output 2

3

Explanation 2  

In this sample $b=\text{"0100101010"}$

One solution is to change the values of $b[2],b[5]\:\text{and}\:b[9]$ to form a beautiful string.

Source: hackerrank | Difficulty: EASY
Tags: String algorithms


Solutions:
import re
import sys
n = int(input().strip())
B = input().strip()
print(len(re.findall('010', B)))


m = int(input())
n = str(input().strip())
print(n.count('010'))


n = int(input())
s = input()
print(s.count('010'))


import sys
n = int(input().strip())
B = list(input().strip())
ans = 0
for i in range(n - 2):
	if B[i] == '0' and B[i + 1] == '1' and (B[i + 2] == '0'):
		ans += 1
		B[i + 2] = '1'
print(ans)


import sys
n = int(input().strip())
B = input().strip()
i = 2
count = 0
while i < n:
	if B[i - 2:i + 1] == '010':
		count += 1
		i += 2
	i += 1
print(count)


import sys
n = int(input().strip())
B = list(input().strip())
ans = 0
for k in range(n):
	for i in range(n - 2):
		if ''.join(B[i:i + 3]) == '010':
			B[i + 2] = '1'
			ans += 1
			break
print(ans)


n = int(input())
B = list(input())
counter = 0
for i in range(1, n - 1):
	if B[i] == '1' and B[i - 1] == '0' and (B[i + 1] == '0'):
		B[i + 1] = '1'
		counter += 1
print(counter)


import sys
n = int(input().strip())
B = list(input().strip())
c = 0
for i in range(n - 2):
	if B[i:i + 3] == list('010'):
		j = i + 2
		B[j] = '1'
		c += 1
print(c)


n = int(input().strip())
s = input().strip()
c = 0
c = s.count('010')
print(c)


import sys
n = int(input().strip())
B = list(input().strip())
c = 0
for i in range(n - 2):
	if B[i:i + 3] == ['0', '1', '0']:
		B[i + 2] = '1'
		c += 1
print(c)


import re
n = int(input().strip())
B = input().strip()
(B1, rep) = re.subn('010', '011', B)
print(rep)


import sys
n = int(input().strip())
B = input().strip()
delta = 0
while '01010' in B:
	idx = B.index('01010')
	B = B[:idx + 2] + '1' + B[idx + 3:]
	delta += 1
while '010' in B:
	idx = B.index('010')
	B = B[:idx + 1] + '0' + B[idx + 2:]
	delta += 1
print(delta)


import sys
n = int(input().strip())
B = input().strip()
if n < 3:
	print(0)
else:
	total = 0
	i = 2
	while i < n:
		if B[i - 2:i + 1] == '010':
			total += 1
			i += 3
		else:
			i += 1
	print(total)


import sys
n = int(input().strip())
B = list(input().strip())
cnt = 0
for i in range(3, n + 1):
	if B[i - 3:i] == ['0', '1', '0']:
		B[i - 1] = '1'
		cnt += 1
print(cnt)


n = int(input())
txt = input().strip()
cnt = 0
i = 0
while i < n:
	if i < n - 2 and txt[i] == '0' and (txt[i + 1] == '1') and (txt[i + 2] == '0'):
		cnt += 1
		txt[i + 2] == '1'
		i += 2
	i += 1
print(cnt)


import sys
n = int(input().strip())
B = input().strip()
steps = 0
while True:
	pos = B.find('010')
	if pos == -1:
		break
	else:
		steps += 1
		B = B[pos + 3:]
print(steps)


import sys
n = int(input().strip())
B = map(int, input().strip())
counter = 0
two_back = 2
one_back = 2
for i in B:
	if i == 0 and one_back == 1 and (two_back == 0):
		counter += 1
		one_back = 1
		two_back = 1
		continue
	(two_back, one_back) = (one_back, i)
print(counter)


import sys
n = int(input().strip())
B = input().strip()
B2 = B.replace('01010', '01110')
B2 = B2.replace('010', '011')
k = 0
for i in range(len(B)):
	if B[i] != B2[i]:
		k += 1
print(k)


import sys
n = int(input().strip())
B = input().strip()
res = 0
i = 0
while i < n - 2:
	count = 0
	while B[i:i + 3] == '010':
		count += 1
		i += 2
	if count % 2 == 0:
		res += int(count / 2)
	else:
		res += int(count / 2) + 1
	i += 1
print(res)


input()
b = list(input())
ans = 0
for i in range(len(b) - 2):
	if b[i] == '0' and b[i + 1] == '1' and (b[i + 2] == '0'):
		b[i + 2] = '1'
		ans += 1
print(ans)


n = int(input().strip())
l = list(input().strip())
r = 0
while len(l) >= 3:
	if l[0] == '0' and l[1] == '1' and (l[2] == '0'):
		r += 1
		if len(l) > 3 and l[3] == '1':
			l[2] = '1'
		else:
			l[1] = '0'
	l = l[1:]
print(r)


import sys
n = int(input().strip())
B = input().strip()
c = 0
S = B.replace('010', '011')
for i in range(len(B)):
	if B[i] != S[i]:
		c += 1
print(c)


import re
n = int(input().strip())
B = input().strip()
exp = re.compile('010')
print(len(exp.findall(B)))


import sys
import re
n = int(input().strip())
B = input().strip()
print(len(re.findall('(010)', B)))


import sys
n = input()
a = input()
a = list(a)
count = 0
for i in range(len(a) - 2):
	if a[i] == '0' and a[i + 1] == '1' and (a[i + 2] == '0'):
		a[i + 2] = '1'
		count += 1
print(count)


import sys
n = int(input().strip())
B = input().strip()
C = B.split('010')
k = 0
for var in C:
	k = k + len(var)
print(int((n - k) / 3))


import sys
n = int(input().strip())
B = input().strip()
pattern = '010'
count = 0
while True:
	x = B.find(pattern)
	if x < 0:
		break
	count = count + 1
	B = B[x + 3:]
print(count)


import sys
a = 0
n = int(input().strip())
B = [int(b_temp) for b_temp in input().strip()]
for i in range(n - 2):
	if B[i] == 0 and B[i + 1] == 1 and (B[i + 2] == 0):
		B[i + 2] = 1
		a += 1
print(a)


import sys
n = int(input().strip())
B = input().strip()
times = 0
while '010' in B:
	B = B.replace('010', '011', 1)
	times += 1
print(times)


import sys
n = int(input().strip())
B = input().strip()
c = 0
l = B.find('010')
while l > -1:
	B = B.replace('010', '011', 1)
	l = B.find('010')
	c += 1
print(c)


import sys
n = int(input().strip())
B = input().strip()
if '010' not in B:
	print(0)
else:
	num = 0
	while True:
		if '01010' in B:
			B = B.replace('01010', '01110', 1)
			num = num + 1
		elif '010' in B:
			B = B.replace('010', '000', 1)
			num = num + 1
		else:
			break
	print(num)


def chan(stri, point):
	if stri[point] == 0:
		stri[point] = 1
	elif stri[point] == 1:
		stri[point] = 0
	return stri
temp = []
cont = 0
n = int(input())
stri = input().strip()
for k in range(n - 2):
	if stri[0 + k:0 + k + 3] == '010':
		if not k - 2 in temp:
			stri = chan(stri, k + 2)
			cont += 1
			temp.append(k)
print(cont)


import sys
n = int(input().strip())
B = input().strip()
j = 0
for i in range(n):
	if '01010' in B:
		catch = B.find('01010')
		lstB = list(B)
		lstB[catch + 2] = '1'
		B = ''.join(lstB)
		j += 1
		pass
	elif '010' in B:
		catch = B.find('010')
		lstB = list(B)
		lstB[catch] = '1'
		B = ''.join(lstB)
		j += 1
		pass
print(j)


import sys
n = int(input().strip())
B = input().strip()
B = [i for i in B]
i = 0
cnt = 0
while i < n - 2:
	temp = B[i:i + 3]
	if ''.join(temp) == '010':
		cnt += 1
		i = i + 3
	else:
		i += 1
print(cnt)


import sys
n = int(input().strip())
B = input().strip()
int_b = [int(x) for x in B]
count = 0
for i in range(len(int_b)):
	if int_b[i:i + 3] == [0, 1, 0]:
		int_b[i + 2] = 1
		count += 1
print(count)


def unbeautify(s):
	l = [int(ch) for ch in s]
	i = 0
	count = 0
	while i < len(l) - 2:
		if l[i:i + 3] == [0, 1, 0]:
			l[i + 2] = 1
			count += 1
			i += 2
		i += 1
	return count

def test():
	res = unbeautify('0101010')
	assert res == 2
	res = unbeautify('01100')
	assert res == 0
	res = unbeautify('0100101010')
	assert res == 3

def main():
	_ = input().strip()
	s = input().strip()
	print(unbeautify(s))
main()


import sys
n = int(input().strip())
B = input().strip()
bb = [i for i in B]
strn = '010'
c = 0
while True:
	a = B.find(strn)
	if a >= 0:
		bb[a + 2] = '1'
		B = ''.join(bb)
		c += 1
	else:
		break
print(c)


n = int(input().strip())
b = input().strip()
(i, step) = (0, 0)
while i < n - 2:
	if b[i] + b[i + 1] + b[i + 2] == '010':
		step += 1
		i += 2
	i += 1
print(step)


import sys
n = int(input().strip())
B = [x for x in input().strip()]
steps = 0
for i in range(2, n):
	if B[i - 2] == '0' and B[i - 1] == '1' and (B[i] == '0'):
		B[i] = '1'
		steps += 1
print(steps)


import sys
n = int(input().strip())
B = input().strip()
if len(B) < 3:
	print(0)
else:
	count = 0
	Blist = list(B)
	for i in range(1, len(Blist) - 1):
		if Blist[i] == '1' and Blist[i - 1] == '0' and (Blist[i + 1] == '0'):
			count += 1
			Blist[i + 1] = '1'
	print(count)


import sys
n = int(input())
s = input().strip()
s = [x for x in s]
cnt = 0
for i in range(len(s)):
	v = ''.join([c for c in s[i:i + 3]])
	if v == '010':
		s[i + 2] = '1'
		cnt += 1
print(cnt)


n = int(input())
s = input()
i = 1
ans = 0
while i < n - 1:
	if s[i - 1:i + 2] == '010':
		ans += 1
		i += 3
	else:
		i += 1
print(ans)


import sys
import re
n = int(input().strip())
B = input().strip()
ugly = '010'
counter = 0
for ugly in B:
	if B.find('010') != -1:
		B = re.sub('010', '011', B, 1)
		counter += 1
print(counter)


import sys
import re
n = int(input().strip())
B = input().strip()
matches = re.findall('010', B)
print(len(matches))


import sys
n = int(input().strip())
B = input().strip()
print(len(B.split('010')) - 1)


_010 = ['0', '1', '0']

def minSteps(s):
	steps = 0
	for i in range(0, n - 2):
		if s[i:i + 3] == _010:
			s[i + 2] = 1
			steps += 1
	return steps
n = int(input().strip())
B = list(input().strip())
print(min(minSteps(list(B)), minSteps(B[::-1])))


import sys
n = int(input().strip())
B = list(input().strip())
ans = 0
for i in range(n - 2):
	if B[i] == '0' and B[i + 1] == '1' and (B[i + 2] == '0'):
		ans += 1
		B[i + 2] = '1'
print(ans)


import sys
n = int(input().strip())
b = input().strip()
c = b.count('010')
print(c)


import sys
from collections import Counter
n = int(input().strip())
B = input().strip()
c = B.count('010')
print(c)


import sys
n = int(input().strip())
B = input().strip()
C = B
count = 0
i = 0
while i < len(B) - 2:
	if B[i:i + 3] == '010':
		C = C[:i + 2] + '.' + C[i + 3:]
		count += 1
		i += 3
	else:
		i += 1
print(count)


N = int(input())
B = input().strip()
d = 0
i = B.find('010')
while i >= 0:
	d += 1
	i = B.find('010', i + 3)
print(d)


import sys
n = int(input().strip())
B = input().strip()

def beautify(my_str):
	if len(my_str) in range(3):
		return 0
	for i in range(len(my_str) - 2):
		if my_str[i:i + 3] == '010':
			return 1 + beautify(my_str[i + 3:])
	return 0
print(beautify(B))


import sys
n = int(input().strip())
B = input().strip()
count = 0
x = 0
leftIndex = -1
prevIndex = -1
overlap = 0
while x < len(B):
	leftIndex = B.find('010', x)
	if leftIndex != -1:
		count += 1
		if prevIndex + 2 == leftIndex:
			overlap += 1
		elif overlap > 0:
			if overlap > 2:
				count -= 2
			else:
				count -= 1
			overlap = 0
		prevIndex = leftIndex
		x = leftIndex + 2
	else:
		x += 1
if overlap > 0:
	if overlap > 2:
		count -= 2
	else:
		count -= 1
print(count)


import sys
n = int(input().strip())
B = input().strip()
if '010' not in B:
	print(0)
else:
	print(B.count('010'))


from sys import stdin

def BeautifulBinaryString(n: int, B: str) -> int:
	assert len(B) == n
	assert set(B).issubset({'0', '1'})
	return B.count('010')
INPUT = stdin.read().strip().splitlines()
OUTPUT = BeautifulBinaryString(int(INPUT[0]), INPUT[1])
print(OUTPUT)


import sys
import re
n = int(input().strip())
B = input().strip()
mos = re.findall('010', B)
print(len(mos))


n = int(input().strip())
B = input().strip()
c = 0
while '010' in B:
	B = B[B.index('010') + 3:]
	c += 1
print(c)


import sys

def solve(a):
	(cnt, i) = (0, 0)
	while i < len(a):
		j = a.find('010', i)
		if j == -1:
			break
		if j < len(a) - 6 and a[j:j + 5] == '01010':
			cnt += 1
			i = j + 4
		else:
			cnt += 1
			i = j + 3
	return cnt
n = int(input().strip())
B = input().strip()
print(solve(B))


import sys
n = input()
B = input()
print(B.count('010'))


n = int(input())
s = input()
print(s.count('010'))


import sys
n = int(input().strip())
B = input().strip()
l = B.count('010')
print(l)


def read_int():
	return int(input().strip())

def read_string():
	return str(input().strip())
N = read_int()
bs = read_string()
L = len(bs)
i = 0
count = 0
while i < L:
	if bs[i:i + 5] == '01010':
		count += 1
		i += 4
		continue
	if bs[i:i + 3] == '010':
		count += 1
		i += 3
		continue
	i += 1
print(count)


input()

def beautify(s):
	result = 0
	for i in range(len(s) - 2):
		if s[i:i + 3] == '010':
			s = s[:i + 2] + '1' + s[i + 3:]
			result += 1
	return result
print(beautify(input()))


(n, B) = (input(), input())
nchanges = 0
while '010' in B:
	B = B.replace('010', 'XXX', 1)
	nchanges += 1
print(nchanges)


n = int(input().strip())
B = input().strip()
l = list()
for i in B:
	l.append(i)
c = 0
for i in range(0, n - 2, 1):
	if l[i] + l[i + 1] + l[i + 2] == '010':
		c = c + 1
		l[i + 2] = '1'
print(c)


import sys
import re
n = int(input().strip())
B = input().strip()
count = 0
x = re.findall('010', B)
print(len(x))


import sys
k = 0
a = False
n = int(input().strip())
B = input().strip()
while a == False:
	if B.find('010') > -1:
		a = False
		B = B.replace('010', '011', 1)
		k += 1
	else:
		a = True
print(k)


import sys
n = int(input().strip())
B = input().strip()
count = B.count('010')
print(count)


n = int(input().strip())
B = input().strip()
print(B.count('010'))


n = int(input())
s = input()
count = 0
for i in range(2, n, 1):
	if s[i - 2] == '0' and s[i - 1] == '1' and (s[i] == '0'):
		if i + 1 <= len(s) - 1 and s[i + 1] == '1':
			s = s[:i] + '1' + s[i + 1:]
		else:
			s = s[:i - 1] + '0' + s[i:]
		count += 1
print(count)


import sys
n = int(input().strip())
b = input().strip()
c = 0
while '010' in b:
	i = b.index('010')
	b = b[:i] + '011' + b[i + 3:]
	c += 1
print(c)


import sys
n = int(input().strip())
b = input().count('010')
print(b)


import sys
print(input() * False, input().count('010'), sep='')


import sys
count = input()
string = str(input())
print(string.count('010'))


import sys
n = int(input().strip())
B = input().strip()
cnt = 0
i = 0
while i < len(B) - 2:
	if B[i:i + 3] == '010':
		cnt += 1
		i += 2
	i += 1
print(cnt)


input()
print(input().count('010'))


import sys
n = int(input().strip())
B = input().strip()
if n <= 2:
	print(0)
else:
	(p1, p2) = (B[0], B[1])
	count = 0
	for i in range(2, n):
		c = B[i]
		if p1 + p2 + c == '010':
			count += 1
			p1 = p2
			p2 = '1'
		else:
			p1 = p2
			p2 = c
	print(count)


import sys
n = int(input().strip())
B = input().strip()
print(B.count('010'))


import sys
n = int(input().strip())
B = input().strip()
l = [int(n) for n in B]
r = 0
for ind in range(0, len(l) - 2):
	if l[ind] == 0 and l[ind + 1] == 1 and (l[ind + 2] == 0):
		try:
			l[ind + 2] = 1
			r += 1
		except:
			pass
print(r)


import sys
n = int(input().strip())
B = list(input().strip())
count = 0
for b1 in range(0, n - 2):
	if B[b1] == '0' and B[b1 + 1] == '1' and (B[b1 + 2] == '0'):
		B[b1 + 2] = '1'
		count += 1
print(count)


import sys
import re
n = int(input().strip())
B = input().strip()
dfa = re.compile('010')
match = dfa.search(B)
count = 0
while match:
	count += 1
	if match.end() < len(B):
		B = B[match.end():]
	else:
		break
	match = dfa.search(B)
print(count)


import sys
n = int(input().strip())
B = input().strip()
print(B.count('010'))


import sys
n = int(input().strip())
B = input().strip()
print(B.count('010'))


import sys
n = int(input().strip())
B = input().strip()
b = []
for i in range(0, len(B)):
	b.append(B[i])
if n < 3:
	print(0)
else:
	cnt = 0
	for i in range(3, n + 1):
		if b[i - 3] == '0' and b[i - 2] == '1' and (b[i - 1] == '0'):
			b[i - 1] = '1'
			cnt = cnt + 1
	print(cnt)


import sys
n = input().strip()
B = input().strip()
print(B.count('010'))


import sys
n = int(input().strip())
B = str(input().strip())
solved = False
count = 0
while not solved:
	index = B.find('010')
	if index != -1:
		l = list(B)
		l[index + 2] = '1'
		B = ''.join(l)
		count += 1
	else:
		solved = True
print(count)


import sys
n = int(input().strip())
B = list(input().strip())
TARGET = list('010')
steps = 0
for i in range(n - 2):
	if B[i:i + 3] == TARGET:
		B[i + 2] = '1'
		steps += 1
print(steps)


import sys
n = int(input().strip())
B = input().strip()
cnt = 0
for i in range(n - 2):
	if B[i:i + 3] == '010':
		Bnew = B[:i] + '011' + B[i + 3:]
		B = Bnew
		cnt += 1
print(cnt)


import sys
end = int(input().strip())
string = input().strip()
pattern = '010'
start = 0
counter = 0
while start > -1 and start < end:
	start = string.find(pattern, start)
	if start > -1:
		counter += 1
		start += len(pattern)
print(counter)


import sys
n = int(input().strip())
B = input().strip()
print(B.count('010'))


import sys
n = int(input().strip())
B = list(input().strip())
counter = 0
for pos in range(n - 2):
	if B[pos:pos + 3] == ['0', '1', '0']:
		B[pos + 2] = '1'
		counter += 1
print(counter)


import sys
n = int(input().strip())
B = input().strip()
prev_end = -1
start = 0
operations = 0
while start < n:
	if B[start] == '0' and B[start:start + 3] == '010':
		if start > prev_end:
			operations += 1
			prev_end = start + 2
		start += 2
	else:
		start += 1
print(operations)


import sys
n = int(input().strip())
B = input().strip()
i = 0
result = 0
while i < n:
	if B[i:i + 3] == '010':
		i += 3
		result += 1
	else:
		i += 1
print(result)


import sys
n = int(input().strip())
b = list(input().strip())
c = 0
count = 0
while c < len(b) - 2:
	if b[c] == '0':
		if b[c + 1] == '1':
			if b[c + 2] == '0':
				b[c + 2] = '1'
				count += 1
			else:
				c += 3
		else:
			c += 1
	else:
		c += 1
print(count)


import sys
n = int(input().strip())
B = input().strip()

def solution(number):
	return B.count('010')
print(solution(B))


import sys
n = int(input())
s = input()
pattern = '010'
op = 0
flag = s.find(pattern)
while flag != -1:
	if len(s) > flag + 3:
		s = s[:flag + 2] + '1' + s[flag + 3:]
	else:
		s = s[:flag + 2] + '1'
	flag = s.find(pattern)
	op += 1
print(op)


import sys
n = int(input().strip())
B = input().strip()
c = 0
for i in range(len(B) - 2):
	if B[i:i + 3] == '010':
		B = B[:i] + '011' + B[i + 3:]
		c += 1
print(c)


import sys
n = int(input().strip())
B = list(input().strip())
res = 0
for i in range(n - 2):
	if B[i] == '0' and B[i + 1] == '1' and (B[i + 2] == '0'):
		B[i + 2] = '1'
		res += 1
print(res)


import sys
n = int(input().strip())
B = input().strip()
l = list(B)
count = 0
for i in range(len(l) - 2):
	if (B[i:i + 3] == '010') & (l[i] == '0'):
		l[i + 2] = '1'
		count += 1
print(count)


import sys
n = int(input().strip())
B = input().strip()
res = 0
while True:
	i = B.find('0101')
	if i == -1:
		break
	B = B[:i] + '0111' + B[i + 4:]
	res += 1
while True:
	i = B.find('010')
	if i == -1:
		break
	B = B[:i] + '011' + B[i + 3:]
	res += 1
print(res)