Problem:


Score : 300 points

Problem Statement

There are N stones arranged in a row. Every stone is painted white or black.
A string S represents the color of the stones. The i-th stone from the left is white if the i-th character of S is ., and the stone is black if the character is #.

Takahashi wants to change the colors of some stones to black or white so that there will be no white stone immediately to the right of a black stone.
Find the minimum number of stones that needs to be recolored.

Constraints

1 \leq N \leq 2\times 10^5

S is a string of length N consisting of . and #.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the minimum number of stones that needs to be recolored.

Sample Input 1

3
#.#

Sample Output 1

1

It is enough to change the color of the first stone to white.

Sample Input 2

5
#.##.

Sample Output 2

2

Sample Input 3

9
.........

Sample Output 3

0



Sample input:
3
#.#


Sample output:
1

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())
n=0
s=S[::-1]
for i in range(len(S)):
    if s[i]=="#":
        n+=1
    else:
        break
#print(n)

B=0
W=0
Flag=0
L=[]
P="#"
CNT=0
for i in range(len(S)-n):
    if S[i]=="#":
        Flag=1
    if Flag==1:
        if S[i]=="#":
            if P=="#":
                CNT+=1
            else:
                L.append(CNT)
                P="#"
                CNT=1
        else:
            if P==".":
                CNT+=1
            else:
                L.append(CNT)
                P="."
                CNT=1
L.append(CNT)
#print(L)
#print(S)
if len(L)<2:
    print(0)
elif len(L)>=2:
    
    E=[0]
    O=[0]
    for  i in range(len(L)):
        if i%2==0:
            E.append(E[len(E)-1]+L[i])
        else:
            O.append(O[len(O)-1]+L[i])
    
    #print(E,O)
    #for i in range(len(E)):
    MIN=10**20
    for i in range(len(E)):
        if MIN>(E[i]+O[len(O)-1]-O[i]):
            MIN=(E[i]+O[len(O)-1]-O[i])
    print(MIN)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)


N = int(input())
S = input()
S = list(S)


indices_black = list()
for i, c in enumerate(S):
    if c == '#':
        indices_black.append(i)

count_white = dict()
count = 0
for i, c in enumerate(S[::-1]):
    if c == '.':
        count += 1
    count_white[N - i - 1] = count


def get_answer(S):
    # most left
    if len(indices_black) == 0:
        return 0

    idx = indices_black.pop(0)
    if count_white[idx] == 0:
        return 0
    # count white: turn all white -> black
    ans_w = count_white[idx]

    # turn most left black -> white
    S[idx] = '.'
    ans_b = get_answer(S) + 1
    return min(ans_w, ans_b)


print(get_answer(S))

Submission status: Accepted

Solution code:
import sys

N = int(input())
S = input()

if "#" not in S or "." not in S:
    print(0)
    sys.exit(0)

# all_dot = len([s for s in S if s == "#"])

ans = 1e20
num = 0
all_dot = int(S[0]=="#")
for i in range(1, len(S)):
    if S[i-1] == "." and S[i] == "#":
        num = min(num, all_dot)

    if S[i] == '#':
        all_dot += 1
    else:
        num += 1

ans = min(all_dot, num)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
S = '.' + S

b_tot, w_tot = 0, 0
for s in S:
    if s == '.':
        w_tot += 1
    else:
        b_tot += 1

b_left, w_left = 0, 0
tmp = 3 * 10**5
for s in S:
    if s == '.':
        w_left += 1
    else:
        b_left += 1
    tmp = min(tmp, b_left + w_tot - w_left)
print(tmp)

Submission status: Accepted

Solution code:
def main():
    _ = int(input())
    s = input()
    print(solve(s))

def solve(s):
    n = len(s)

    blacks = [None for _ in range(n + 2)]
    whites = [None for _ in range(n + 2)]
    b = 0
    w = 0

    for i in range(n):
        if s[i] == '#':
            b += 1
        blacks[i + 1] = b

    for i in reversed(range(n)):
        if s[i] == '.':
            w += 1
        whites[i + 1] = w

    blacks[0] = 0
    blacks[n + 1] = blacks[n]
    whites[0] = whites[1]
    whites[n + 1] = 0

    m = float('inf')
    for i in range(n + 1):
        m = min(m, blacks[i] + whites[i + 1])

    return m

main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
w = '.'
b = '#'

c = S.count(w)
c_min = c

for i in range(N):
    if S[i] == b:
        c += 1
    else:
        c += -1
    if c < c_min:
        c_min = c

print(c_min)

Submission status: Accepted

Solution code:
N = int(input())
S = " " + input() + " "

# 左を白、右を黒にする
# 白の個数、黒の個数、白、黒、、、、黒の個数
# という数列を作る
# 0は白、1は黒を意味する
num01 = []
white = 0
black = 0
if("#" == S[1]):
    num01 = [0]
for i in range(1, N + 1):
    if("." == S[i]):
        white += 1
    else:
        black += 1
    if(S[i - 1] != S[i]):
        st = i
    if(S[i] != S[i + 1]):
        num01.append(i - st + 1)
if("." == S[-2]):
    num01.append(0)
#print("num01= {}".format(num01))

minchg = N
# iの右側までを白とする
btow = 0
wtob = white
for i in range(len(num01)):
    if(i % 2):  # b | w
        btow += num01[i]
    else:   # w | b
        wtob -= num01[i]
    minchg = min(minchg, btow + wtob)

print(minchg)

Submission status: Accepted

Solution code:
N = int(input())
s = input()

b_cnt, w_cnt = [0], [0]
for si in s:
    if si==".":
        b_cnt.append(b_cnt[-1])
        w_cnt.append(w_cnt[-1]+1)
    else:
        b_cnt.append(b_cnt[-1]+1)
        w_cnt.append(w_cnt[-1])

b_cnt = b_cnt[1:]
w_cnt = w_cnt[1:]
# print(b_cnt)
# print(w_cnt)
w = s.count(".")
b = s.count("#")
ans = float('inf')
ans = min(w, b)
for i in range(N):
    cond = b_cnt[i] + w - w_cnt[i]
    ans = min(ans, cond)

print(ans)

Submission status: Accepted

Solution code:
raw_input()
t=raw_input()
hayIzqN=[]
hayDerB=[]
N=0
B=0
for i in t:
	if i=="#":
		N+=1
	else:
		B+=1
cant=2000000
blan=0 
hay_n=False
conv=0
b=0
n=0
for i in xrange(len(t)):
	if t[i]=="#":
		hay_n=True
		cant=min(cant, B-b+conv)
		conv+=1
	else:
		b+=1
cant=min(cant, N)
print cant

Submission status: Accepted

Solution code:
import queue

"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
import queue
 
 
N = int(input())
S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
 
ch = False
ans = 0
bl  = 0
b_total = []
w_total = []
tot = 0
for s in S:
	b_total.append(tot)
	if s == "#":
		tot += 1
tot = 0
for s in S:
	if s == ".":
		tot += 1
	w_total.append(tot)
ans = 100000000
for i in range(len(S)):
	ans = min(ans,b_total[i]+w_total[-1]-w_total[i])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    n = int(input())
    s = input()
    lw = 0
    for i in range(len(s)):
        if s[i] == '#':
            break
        lw += 1
    rb = len(s)
    for i in range(len(s)):
        if s[len(s)-i-1] == '.':
            break
        rb -= 1
    w = sum(1 for c in s[lw:rb] if c == '.')
    b = len(s[lw:rb]) - w
    best = min(w, b)
    flag = True
    db = 0
    dw = 0
    s = s[lw:rb]
    # print(dw, db, s)
    for i, c in enumerate(s):
        if flag and c == '#':
            db += 1
            continue
        flag = False
        if c == '.':
            dw += 1
            continue
        # print(dw, db, s[i:])
        best = min(best, w-dw+db)
        db += 1
        flag = True
    best = min(best, w-dw+db)
    print(best)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
S=input()
n=[0]*(N+1)
for i in range(N):
    if S[i]=='#':
        n[i+1]=n[i]+1
    else:
        n[i+1]=n[i]
ans=min(n[-1],N-n[-1])
for i in range(N):
    ans=min(ans,N-i-(n[-1]-n[i])+n[i])
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
b=[0 for i in range(N+1)]

m=0
for i in range(N):
    if S[i]=='#':
        m+=1
    b[i+1]=m

ans=2*b[0]+N-b[-1]

for i in range(1,N+1):
    ans=min(ans,2*b[i]+N-i-b[-1])

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
S=list(input())
if len(set(S))==1:
    print(0)
    exit()
W,B=[0]*n,[0]*n
if S[0]=='.':
    W[0]=1
else:
    B[0]=1
for i in range(1,n):
    if S[i]=='.':
        W[i]=W[i-1]+1
        B[i]=B[i-1]
    else:
        W[i]=W[i-1]
        B[i]=B[i-1]+1
cnt1=float('inf')
for i in range(n-1):
    w=W[i]
    b=B[-1]-B[i]
    tmp=n-w-b
    cnt1=min(cnt1,tmp)
for i in reversed(range(n)):
    if S[i]=='.':
        break
cnt2=S[:i+1].count('#')
for i in range(n-1):
    if S[i]=='#':
        break
cnt3=S[i+1:].count('.')
print(min(cnt1,cnt2,cnt3))

Submission status: Accepted

Solution code:
import sys



fin = sys.stdin.readline
N = int(fin())
S = fin().rstrip("\n")
assert len(S) == N

WHITE, BLACK = 0, 1
# 満たしている状態での処理数
min_changes_at = [[float('inf')] * 2 for _ in range(N)]
min_changes_at[-1] = [1, 0] if S[-1] == "#" else [0, 1]

for i in reversed(range(len(S) - 1)):
    color = S[i]
    if color == "#":
        min_changes_at[i][WHITE] = min(min_changes_at[i + 1]) + 1
        min_changes_at[i][BLACK] = min_changes_at[i + 1][BLACK]
    else:  # WHITE
        min_changes_at[i][WHITE] = min(min_changes_at[i + 1])
        min_changes_at[i][BLACK] = min_changes_at[i + 1][BLACK] + 1
# print(min_changes_at)
print(min(min_changes_at[0]))

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
cum = [[0,0]] #くろ、しろの順
for i in range(n):
    if s[i] == ".":
        cum.append([cum[i][0],cum[i][1]+1])
    else:
        cum.append([cum[i][0]+1,cum[i][1]])
cum.append(cum[-1])
mnm = 1e9
for i in range(n+1):
    if mnm > cum[i][0]-cum[0][0] + cum[-1][1]-cum[i][1]:
        mnm = cum[i][0]-cum[0][0] + cum[-1][1]-cum[i][1]

print(mnm)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
b = [0]*N
w = [0]*N
ans = []
for n in range(N):
    if S[n] == '#':
        if n == 0:
            b[n] = 1
        else:
            b[n] = b[n-1] +1
    else:
        if n == 0:
            b[n] = 0
        else:
            b[n] = b[n-1]

    if S[N-1-n] == '.':
        if N-1-n == N-1:
            w[N-1-n] = 1
        else:
            w[N-1-n] = w[N-n] +1
    else:
        if N-1-n == N-1:
            w[N-1-n] = 0
        else:
            w[N-1-n] = w[N-n]

for n in range(N):
    ans.append(b[n]+w[n])


print(min(ans)-1)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
w = [0]*N
b = [0]*N
s = S[::-1]
for i in range(N):
    b[i] = b[i-1]
    if S[i] == '#':
        b[i] += 1
    w[i] = w[i-1]
    if s[i] == '.':
        w[i] += 1

m = min(w[N-1],b[N-1])
for i in range(N-1):
    m = min(m,b[i]+w[N-i-2])

print(m)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
S=input()

# N=8
# S = ".#...##."

# N = 2*10**5
# S = "#"*N

ls1 = np.empty(N,dtype=np.int)
start = False
cnt1 = 0
for i,s in enumerate(S):
    if (not start) and s == "#":
        start = True
    elif start and s == ".":
        cnt1 += 1
    ls1[i] = cnt1

ls2 = np.empty(N,dtype=np.int)
start = False
cnt2 = 0
for i in range(len(S))[::-1]:
    s = S[i]
    if (not start) and s == ".":
        start = True 
    elif start and s == "#":
        cnt2 += 1
    ls2[i] = cnt2
    
ls11 = ls1.max()-ls1
ls22 = ls2.max()-ls2
# print(ls11+ls22)


print((ls11+ls22).min())

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

white = [0] * N
black = [0] * N

for i in range(N):
    if S[i] == '#':
        white[i] += 1
    else:
        black[i] += 1

for i in range(N-1):
    white[i+1] += white[i]
    black[i+1] += black[i]

ans = min(white[N-1],black[N-1])
for i in range(N-1):
    ans = min(ans,white[i]+(black[-1] - black[i]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

tmp = [0, 0]
flag = False
count1 = 0
for i in s:
    if(i == "."): tmp[0] += 1
    else: tmp[1] += 1
    if(flag == True):
        if(i == "."): count1 += 1
    elif(i == "#"): flag = True


b = [0, 0]
count2 = 1e9
for i in s:
    if(i == "."): b[0] += 1
    else: b[1] += 1
    v = b[1] + tmp[0] - b[0]
    if(count2 > v): count2 = v

s = s[::-1]
flag = False
count3 = 0
for i in s:
    if(flag == True):
        if(i == "#"): count3 += 1
    elif(i == "."): flag = True



print(min([count1, count2, count3]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:58:04 2019

@author: Yamazaki Kenichi
"""

N = int(input())
S = input()

a,b,c = 0,0,0
flg,flg2 = False,False
for i in range(N):
    if S[i] == '.':
        b += 1
        c = min(c+1, a)
    else:
        a += 1
        c = min(a+1,c)
#    print(a,b,c)
print(min(a,b,c))

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b
ans = 100000000
n = int(input())
stones = input()
black = 0
white = 0
for c in stones:
    if c == ".":
        white += 1
ans = white
for c in stones:
    if c == ".":
        white -= 1
    else:
        black += 1
    tmp = black + white
    if ans > tmp:
        ans = tmp

print(ans)

"""
10 
....##....#########.

"""

Submission status: Accepted

Solution code:
N = int(input())
S = input()

w = [0] * N
b = [0] * N
for c in range(N):
    if c == 0:
        if S[c] == '.':
            w[c] = 1
            b[c] = 0
        else:
            w[c] = 0
            b[c] = 1
    else:
        if S[c] == '.':
            w[c] = w[c-1] + 1
            b[c] = b[c-1]
        else:
            w[c] = w[c-1]
            b[c] = b[c-1] + 1

mn = float('inf')
for c in range(N):
    mn = min(mn, b[c] + w[N-1] - w[c])

mn = min(mn, N - w[N-1])
mn = min(mn, N - b[N-1])

print(mn)

Submission status: Accepted

Solution code:
N = input()
S = raw_input()
flag1 = 0
a = 0
count = [0,0]
count2 = []
count3 = []
for c in S:
	if(c == "#"):
		if(flag1 == 1):
			flag1 = 0
			count2.append(count[0])
			count3.append(count[1])
		count[0] += 1
	else:
		count[1] += 1
		flag1 = 1
countf = []
for i in range(len(count2)):
	countf.append(count2[i] + count[1] - count3[i])
countf.append(N - count[0])
countf.append(N - count[1])
print(min(countf))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

w = [0] * N
b = [0] * N
wc = 0
bc = 0
for i in range(N):
  if S[i] == "#":
    wc += 1
  w[i] = wc
for i in range(N - 1, -1, -1):
  if S[i] == ".":
    bc += 1
  b[i] = bc

Ans = w[N - 1]
for i in range(N):
  t = 0
  if i > 1:
    t += w[i - 1]
  t += b[i]
  Ans = min(Ans, t)
print(Ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

wh = 0
bl = 0
a = []
for i in range(n):
    if s[i] == ".":
        wh += 1
    else:
        bl += 1
    a.append([wh,bl])
#print(a)

ans = a[n-1][0]-a[0][0]
for i in range(n):
    k = (a[i][1]) + (a[n-1][0]-a[i][0])
    #print(i,k,(a[i][1]),(a[n-1][0]-a[i][0]))
    ans = min(ans,  k)

print(ans)

Submission status: Accepted

Solution code:
def sub():
    N = int(input())
    S = input()

    black_count = S.count('#')
    white_count = S.count('.')
    # 右側がクロ #, 左を .
    rh_cost = white_count
    lh_cost = 0
    min_cost = rh_cost
    for i in range(N):
        s = S[i]
        if s == '#':
            lh_cost = lh_cost + 1
        else:  # .
            rh_cost = rh_cost - 1

        cost = lh_cost + rh_cost
        if min_cost > cost:
            min_cost = cost
    return min_cost


def main():
    res = sub()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#! -*- coding: utf-8 -*-

n = int(input())
line = input()

w = 0
for i in range(n):
    if line[i] == ".":
        w += 1
b = n-w

w_coutner = 0
b_counter = 0
ans = n
for i in range(n):
    if line[i] == ".":
        w_coutner += 1
    b_counter = i+1 - w_coutner
    wtob = b_counter
    btow = w - w_coutner
    ans_i = wtob + btow
    #print(i,ans_i)
    ans = min(ans,ans_i)

ans = min(w,b,ans)

print(ans)

Submission status: Accepted

Solution code:
n=input()
s=raw_input()
whites=0
for ch in s:
    if ch == ".":
        whites+=1
blacks=n-whites

best=whites #index -1, all stones black
currwhite=0
currblack=0
for ind in range(n):
    if s[ind]==".":
        currwhite+=1
    else:
        currblack+=1
    thisscore = currblack + (whites-currwhite)
    best=min(best,thisscore)
print best

Submission status: Accepted

Solution code:
n = int(input())
s = input()

# All black
isBlack = []
for i in range(len(s)):
    isBlack.append(True if s[i]=='#' else False)
    
cost = len(s) - sum(isBlack)
min_cost = cost

# turning white one by one
for i in range(len(s)):
    if not isBlack[i]:
        cost -= 1
    else:
        cost += 1
        
        
    if cost<min_cost:
        min_cost = cost
print(min_cost)

Submission status: Accepted

Solution code:
N = int(input())
s = input()

BK = '#'

c_bk = [0]
t_bk = 0

c_wt = [0]
t_wt = 0

for ss in s:
    if ss == BK:
        t_bk += 1
    else:
        t_wt += 1

    c_bk.append(t_bk)
    c_wt.append(t_wt)

ans = N
for i in range(0, N + 1):
    to_white = c_bk[i] - c_bk[0]
    to_black = c_wt[N] - c_wt[i]
    ans = min(ans, to_black + to_white)

print(ans)

Submission status: Accepted

Solution code:
#TENKA1-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n=I()
S=S()
B=[0]*n
W=[0]*n
for i in range(n):
    if S[i]=="#":
        B[i]=1
    else:
        W[i]=1
for i in range(n-1):
    B[i+1]+=B[i]
    W[i+1]+=W[i]
B=[0]+B
W=[0]+W
ans=2*n
for i in range(n):
    tans=B[i+1]-B[0]+W[-1]-W[i+1]
    ans=min(ans,tans)
if B[-1]==n:
    ans=0
ans=min(W[-1],ans)
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    s = SI()

    W = [0]
    B = [0]
    for c in s:
        b = c == '#'
        w = c == '.'
        B.append(B[-1] + b)
        W.append(W[-1] + w)

    res = n - max(B[-1], W[-1])
    for i in range(n - 1):
        res = min(res, B[i] + W[-1] - W[i + 1])

    return res


print(main())

Submission status: Accepted

Solution code:
n=int(input())
s=input()
t=[0]
for k in s:t+=[t[-1]+(1 if k=='#' else 0)]
r=[t[i+1]*2+n-i-1-t[-1] for i in range(n)]+[s.count('.')]
print(min(r))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cs = [1 if c=='#' else 0 for c in s]
ans = 0

bs = [0]
for c in cs:
    bs.append(bs[-1]+c)

us = [0]
for c in reversed(cs):
    us.append(us[-1] + 1 - c)
vs = list(reversed(us))

ans = min(bs[i] + vs[i] for i in range(len(bs)))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

cnt_b = s.count("#")
cnt_w = s.count(".")

#全部黒にする
ans = cnt_w
ansa = ans
for i in range(n):
  if s[i] == ".":
     ans -= 1
  else:
     ans += 1
  ansa = min(ans,ansa)
print(ansa)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cum_sum = [0 for _ in range(n)]

for i in range(n):
    if s[i] == '#':
        cum_sum[i] += 1

for i in range(n-1):
    cum_sum[i+1] += cum_sum[i]

#print(cum_sum)

ans = 10 ** 10
for i in range(n):
    tmp = 2 * cum_sum[i] + n - i - 1 - cum_sum[n-1]
    #print(ans, tmp)
    if ans > tmp:
        ans = tmp

tmp = n - cum_sum[n-1]
if ans > tmp:
    ans = tmp

if n == 1:
    print(0)
elif n == cum_sum[-1]:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
s = input()
ans1 = 0
ans2 = 0
DP = [0 for i in range(N)]
s = s[::-1]
if s[0] == ".":
    DP[0] = 1

for i in range(1, N):
    DP[i] = DP[i - 1]
    if s[i] == ".":
        DP[i] += 1

ans = N * 20
DP = DP[::-1]


DP2 = [0 for i in range(N)]
s = s[::-1]
if s[0] == "#":
    DP2[0] = 1

for i in range(1, N):
    DP2[i] = DP2[i - 1]
    if s[i] == "#":
        DP2[i] += 1

ans = DP[0]
for i in range(1, N):
    #print(ans, DP[i] + DP2[i - 1])
    ans = min(ans, DP[i] + DP2[i - 1])
ans = min(ans, DP2[N - 1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
white = [0] * (N + 1)
black = [0] * (N + 1)
bound = [-1]
for i, s in enumerate(S):
    if s == '.':
        white[i + 1] = 1
    else:
        black[i + 1] = 1
    white[i + 1] += white[i]
    black[i + 1] += black[i]
    if i < N - 1 and S[i] == '#' and S[i + 1] == '.':
        bound.append(i)
bound.append(N)

ans = N
for i, j in zip(bound, bound[1:]):
    ans = min(ans, black[i + 1] + white[-1] - white[j])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()

bc = [0]*(N+1)

c = 0
for i,s in enumerate(S):
	if s == '#':
		c += 1
	bc[i+1] = c
abc = bc[-1]

t = [abc-x for x in bc]

ans = N
k = N
for b in bc:
	nb = k - abc + b
	ans = min(ans,nb+b)
	k = k-1
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from sys import exit
N = int(input())
S = input()
if S == '#'*N:
    print(0)
    exit()
W = [int(s == '.') for s in S]
W = list(accumulate(W))
W += [W[-1]]
w = W[-1]
B = [int(s == '#') for s in S]
B = list(accumulate(B))
print(min(w,min(w-i+j for i, j in zip(W, B))))

Submission status: Accepted

Solution code:
N = int(input())
S = input()

x = [0] * (N+1)

for i in range(N):
    if S[i] == '#':
        x[i+1] = x[i] + 1
    else:
        x[i+1] = x[i]

ans = min(N - x[-1], x[-1])
for i in range(1, N):
    ans = min(ans, x[i] + N - i - (x[-1] - x[i]))

print(ans)

Submission status: Accepted

Solution code:

N = int(input())
S = input()

wl = [0]
bl = [0]

w=0
b=0

for i in S:
    if i==".":
        w+=1;
    else:
        b+=1;
    wl.append(w)
    bl.append(b)

wmax = wl[-1]
min = wmax;
for i in range(N+1):
    if wmax+bl[i]-wl[i] < min:
        min = wmax+bl[i]-wl[i]

print(min)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = input()
bl = [0] * (n+1)
wr = [0] * (n+1)
for i in range(n):
    bl[i] = bl[i-1] + (1 if s[i]=='#' else 0)
for i in range(n-1,-1,-1):
    wr[i] = wr[i+1] + (1 if s[i]=='.' else 0)
mn = wr[0]
for i in range(n):
    x = bl[i] + wr[i+1]
    if x < mn:
        mn = x
print(mn)

Submission status: Accepted

Solution code:
n=input()
s=input()
ans=s.count('.')
s1=s.split('#')
s2=[0]
for i in s1:
    s2.append(s2[-1]+len(i))
ans1=ans
for i in range(len(s2)-1):
    ans1=min(ans1,ans-s2[i+1]+i)
print(ans1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    white = []
    white.append(0)
    cur = 0
    for c in S:
        if c == '.':
            cur += 1
        white.append(cur)
    black = []
    black.append(0)
    cur = 0
    for c in S[::-1]:
        if c == '#':
            cur += 1
        black.append(cur)
    black.reverse()
    #print(white)
    #print(black)
    ret = float('inf')
    for i in range(N + 1):
        ret = min(ret, N - (white[i] + black[i]))
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
tow = [0]*(n+1)
tob = [0]*(n+1)
for i in range(n):
    if s[i] == "#":
        tow[i+1] = tow[i]+1
    else:
        tow[i+1] = tow[i]
    if s[n-i-1] == ".":
        tob[i+1] = tob[i]+1
    else:
        tob[i+1] = tob[i]
ans = min(i+j for i, j in zip(tow, tob[::-1]))
print(ans)

Submission status: Accepted

Solution code:
dp = [[0] * 200005 for _ in range(2)]

n = int(input())
s = [1 if c=='.' else 0 for c in input()]

dp[s[0]][0] = 0
dp[s[0]^1][0] = 1

for i, c in enumerate(s[1:]):
    dp[1][i+1] = dp[1][i] + (c^1)
    dp[0][i+1] = min(dp[0][i], dp[1][i]) + c

print(min(dp[0][n-1], dp[1][n-1]))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 998244353

#C
def C():
    n = I()
    s = S()
    ans = float("inf")
    b = [0 for i in range(n)]
    for i in range(n):
        if s[i] == "#":
            b[i] = 1
    w = [0 for i in range(n)]
    for i in range(n):
        if s[i] == ".":
            w[i] = 1
    b.insert(0,0)
    w.insert(0,0)
    for i in range(n):
        b[i+1] += b[i]
        w[i+1] += w[i]
    for i in range(n+1):
        m = b[i]+w[n]-w[i]
        ans = min(ans,m)
    print(ans)
    return

#D
def D():
    n = I()
    a = IR(n)

    return

#E
def E():
    n = I()

    return

#F
def F():
    return


#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())
s = input()

zo = []
zcnt = 0
ocnt = 0
for c in s:
    if c == "#":
        zo.append(1) #black
        ocnt += 1
    else:
        zo.append(0) #white
        zcnt += 1

#print(zcnt,ocnt)
minans = min(ocnt,zcnt)
zcnttill = 0
ocnttill = 0
for i in range(0,n):
    if zo[i] == 0:
        zcnttill += 1
    else:
        ocnttill += 1
    minans = min(minans, ocnttill + (zcnt - zcnttill))

print(minans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
s = input().rsplit()[0]
kuro = [0]*n
siro = [0]*n
for i in range(n):
    if s[i] == "#":
        siro[i]+=1
    if s[-i-1] == ".":
        kuro[-i-1] += 1
    siro[i] += siro[i-1]
    kuro[-i-1] += kuro[-i]
ans = min(kuro[0],siro[-1])
for i in range(1,n):
    ans = min(ans,siro[i-1]+kuro[i])
print(ans)

Submission status: Accepted

Solution code:
N = int( input())
S = input()
C = [0]*(N+1)
for i in range(N):
    if S[i] == ".":
        C[i+1] = C[i]
    else:
        C[i+1] = C[i] + 1
b = C[N]
w = N - b
ans = w
for i in range(N):
    if C[i+1] + N - i - 1 -b + C[i+1] < ans:
        ans = C[i+1] + N - i - 1 -b + C[i+1]
print(ans)

Submission status: Accepted

Solution code:
x=input()
stones=input()
swit=0
maru=0


for st in stones:
    if st=='#':
        maru+=1

l=len(stones)
if maru>l-maru:
    kouho=l-maru
else:
    kouho=maru

minkouho=l-maru
kouho2=l-maru

for st in stones:
    if st=='.':
        kouho2-=1
    else:
        kouho2+=1
    if kouho2<minkouho:
        minkouho=kouho2


print(min(maru,minkouho))

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))

def get_sequence(arr):
    if len(arr) == 0:
        return [], []
    elements = []
    nums = []
    n = 1
    prev = arr[0]
    for c in arr[1:]:
        if c == prev:
            n += 1
        else:
            elements.append(prev)
            nums.append(n)
            prev = c
            n = 1
    elements.append(prev)
    nums.append(n)
    return elements, nums

N = int(input())
S = input()

ele, num = get_sequence(S)
B = S.count('#')
W = N - B

if ele[0] == '#':
    ans = W
    i = 1
else:
    ans = W - num[0]
    i = 2

M = len(num)
cur = ans
while i < M:
    cur += num[i-1]-num[i]
    ans = min(ans,cur)
    i += 2

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
#n = 10 ** 5
stones = [0 if x == "." else 1 for x in list(input())]
#stones = [0] + [0 for _ in range(n)] + [1]

bf = 0
af = n - sum(stones)
min_num = bf + af

for i in range(n):
	bf += stones[i]
	af -= 1 - stones[i]
	min_num = min(min_num, bf + af)

print(min_num)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
B = [0] * N
W = [0] * N
for i in range(N):
    B[i] = B[i - 1]
    W[i] = W[i - 1]
    if S[i] == '#':
        B[i] += 1
    else:
        W[i] += 1
ans = W[N - 1]
for i in range(N):
    ans = min(ans, B[i] + W[N - 1] - W[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return POW(x, y // 2) ** 2 % MOD
    else:
        return POW(x, y // 2) ** 2 * x % MOD
def mod_factorial(x, y): return x * POW(y, MOD - 2) % MOD
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter

def main():
    N = II()
    S = SI()
    b, w = 0, 0
    w = S.count('.')
    ans = w
    for s in S:
        if s == '.':
            w -= 1
        else:
            b += 1
        if w + b < ans:
            ans = w + b
    return ans

print(main())

Submission status: Accepted

Solution code:
n = int(input())
s = input()
s = s+'_'
white = [0]*(n+1)
black = [0]*(n+1)
for i in range(n):
	if s[i] == '#':
		black[i+1] = black[i] + 1
	else:
		black[i+1] = black[i]
for i in range(n-1,-1,-1):
	if s[i]	== '.':
		white[i] = white[i+1] + 1
	else:
		white[i] = white[i+1]

tmpmin = float('inf')
for i in range(n+1):
	tmp = black[i]+white[i]
	if tmpmin > tmp:
		tmpmin = tmp

print(tmpmin)

Submission status: Accepted

Solution code:
from itertools import accumulate as ac
n=int(input())
s=input()
a=[0 if i=="#" else 1 for i in s]
p=[0]+list(ac(a))
b=p[-1]
d=float("inf")
for i in range(n+1):
    d=min(i-p[i]+(b-p[i]),d)
print(d)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
li=[0]
ans=n
for i in s:
    li+=[li[-1]+1] if i=='#' else [li[-1]]
b=li[-1]
for i in range(n+1):
    temp=li[i]+n-i-b+li[i]
    ans=min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    s = input().strip()

    cnt = [0] * n
    for i in range(n):
        if i == 0 and s[0] == '#':
            cnt[0] = 1

        if i>0 :
            if s[i]=='#':
                cnt[i] = 1 + cnt[i-1]
            else:
                cnt[i] = cnt[i-1]
    
    ans = 2e5+5
    for i in range(n):
        ans = min(ans, cnt[i] + n + cnt[i] - cnt[n-1] - (i+1))
    
    ans = min(ans, n - cnt[n-1])
    print(ans)
        

solve()

Submission status: Accepted

Solution code:
n=int(input())
l=list(input())
check=False
cnt=0
cnt1=0
s=[]
for i in range(n):
    if l[i]=='#':
        cnt+=1
s.append(cnt)
for i in range(n-1,-1,-1):
    if l[i]=='.':
        cnt+=1
    else:
        cnt+=-1
    s.append(cnt)
print(min(s))