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 = input()

w_cnt = 0
w_list = []
b_cnt = 0
b_list = []
for i in range(N):
    if S[i] == '#':
        w_cnt += 1
        w_list.append(w_cnt)
    else:
        w_list.append(w_cnt)

    if S[N-1-i] == '.':
        b_cnt += 1
        b_list.append(b_cnt)
    else:
        b_list.append(b_cnt)



ans = N
for i in range(N):
    wa = w_list[i] + b_list[N-2-i]
    if ans > wa:
        ans = wa


if b_list[N-1] < ans:
    ans = b_list[N-1]

if w_list[N-1] < ans:
    ans = w_list[N-1]

print(ans)

Submission status: Accepted

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

cnt=0
l = []
b = 1 if S[0] == "." else 0

for i in range(1, N):
    if S[i]==S[i-1]:
        cnt += 1
        if i == N-1:
            l.append(cnt+1)
    else:
        l.append(cnt+1)
        if i == N-1:
            l.append(1)
        cnt = 0

if len(l)<=1:
    print("0")
    exit()

s = 0
q = 0
q2 = 0
for c in S:
    if c=="#":
        q += 1
    else:
        q2 += 1

for j in range(abs(b-1), len(l), 2):
    #print(j, l[j])
    s += l[j]

m = min(q,q2,s)
#print(s)
for j in range(b, len(l), 2):
    #print(j-2,l[j-2], j-1, l[j-1])
    if j-2 >= 0:
        s += l[j-2]-l[j-1]
    elif j-1 >= 0:
        s += -l[j-1]
    m = min(s, m)


#print(l)
print(m)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
s = input()

blacks = [0]
count = 0

for ele in s:
	if ele == '#':
		count += 1
	blacks.append(count)

whites = [0]
count = 0

for ele in s[::-1]:
	if ele == '.':
		count += 1
	whites.append(count)
#print(blacks)
#print(whites)

blacks = np.array(blacks)
whites = np.array(list(reversed(whites)))

totals = np.add(blacks, whites)
#print(totals)

print(min(totals))

Submission status: Accepted

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

r1=S.count("#")
r2=N-r1
c1=r1
c2=r2


it1=0
it2=N-1
it1f=False
it2f=False
r3=0
isLeft=None

while it1<it2:
  if S[it1]!=".":
    if it1f==True and it2f==True and c1<=c2:
      r3+=1
      it1+=1
      it1f=False
      c1-=1
    else:
      it1f=True
  else:
    it1+=1
    c2-=1

  if S[it2]!="#":
    if it1f==True and it2f==True and c1>c2:
      r3+=1
      it2-=1
      it2f=False
      c2-=1
    else:
      it2f=True
  else:
    it2-=1
    c1-=1

print(r3)

Submission status: Accepted

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

#case1
CT=0
for j in range(len(S)):
    if S[j] == ".":
        CT+=1

#NG: #.
#OK: .#
CH=0
A=CT+CH
for i in range(len(S)):
    if S[i] == ".":
        CT-=1
    if S[i] == "#":
        CH+=1

    A=min(CT+CH, A)


print(A)

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
S = input()
L = list()
for s in S:
    if s == '.':
        L.append(0)
    else:
        L.append(1)

sharp_cumsum = [0] + list(accumulate(L))
period_cumsum = ([0] + list(accumulate([x^1 for x in L[::-1]])))[::-1]

ans = 10 ** 9

for i in range(N):
    left = i
    right = i+1
    tmp_ans = sharp_cumsum[left] + period_cumsum[right]
    ans = tmp_ans if tmp_ans < ans else ans
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    res = w = s.count('.')
    b = 0
    for i in range(n):
        if s[i] == '#':
            b += 1
        else:
            w -= 1
        res = min(res,b+w)

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = N
b_list = [0]
w_list = [0]
for i, s in enumerate(S):
    if s == '#':
        b_list.append(b_list[i]+1)
    else:
        b_list.append(b_list[i])
for i, s in enumerate(reversed(S)):
    if s == '.':
        w_list.append(w_list[i]+1)
    else:
        w_list.append(w_list[i])

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

Submission status: Accepted

Solution code:
n=int(input())
s=list(str(input()))
w=0
b=0
wl=[]
bl=[]
for i in range(n):
    if s[i]==".":
        w+=1
    else:
        b+=1
    wl.append(w)
    bl.append(b)
if "#" not in s or "." not in s:
    print(0)
elif s.count(".")==1 and s[0]=="#":
    print(1)
else:
    ans=[]
    for i in range(n):
        ans.append(bl[i]+wl[-1]-wl[i])
    print(min(min(ans),wl[-1],bl[-1]))

Submission status: Accepted

Solution code:
n=int(input())
s_o=input()
s_dot=[len(x) for x in s_o.replace("#"," ").split()]
s_sharp=[len(x) for x in s_o.replace("."," ").split()]
if s_o[0]==".":
  s_dot=s_dot[1:]
if s_o[-1]=="#":
  s_sharp=s_sharp[:-1]
length=len(s_dot)+1
if len(s_dot)==0 or len(s_sharp)==0:
  print(0)
  exit()
sum_sharp=[0]*length
sum_dot=[0]*length
for i in range(length):
  if i==0:
    sum_sharp[i]=0
  else:
    sum_sharp[i]=sum_sharp[i-1]+s_sharp[i-1]

for i in reversed(range(length)):
  if i==length-1:
    sum_dot[i]=0
  else:
    sum_dot[i]=sum_dot[i+1]+s_dot[i]
ans=[1000000]*(length)
for i in range(length):
  ans[i]=sum_sharp[i]+sum_dot[i]
print(min(ans))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
s = list(input())
b = [0]*(n+1)
c = [s.count(".")]*(n+1)
a = []
a.append(c[0])
for i in range(n):
    if s[i] == "#":
        b[i+1] = b[i] + 1
        c[i+1] = c[i]
    else:
        c[i+1] = c[i] - 1
        b[i+1] = b[i]
    a.append(b[i+1] + c[i+1])
if "." not in s:
    a.append(0)
elif "#" not in s:
    a.append(0)
print(min(a))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
A = [S.count(".")]
for i in range(N):
	if S[i] == "#":
		A.append(A[i] + 1)
	else:
		A.append(A[i] - 1)
print(min(A))

Submission status: Accepted

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

cnt_b = [0 for i in range(N)]    # i番目を含んでにそれまでにb，wが何個あるか
cnt_w = [0 for i in range(N)]

if S[0] == "#":
    cnt_b[0] = 1
else:
    cnt_w[0] = 1

for i in range(1, N):
    if S[i] == "#":
        cnt_b[i] = cnt_b[i-1] + 1
        cnt_w[i] = cnt_w[i-1]
    else:
        cnt_b[i] = cnt_b[i-1]
        cnt_w[i] = cnt_w[i-1] + 1

cnt_change_to_w = [0 for i in range(N)]
cnt_change_to_b = [0 for i in range(N)]
for i in range(N):
    cnt_change_to_b[i] = cnt_b[i] + cnt_w[N - 1] - cnt_w[i]

for i in range(N):
    cnt_change_to_w[i] = cnt_b[i] + cnt_w[N - 1] - cnt_w[i]
    if S[i] == "#":
        cnt_change_to_w[i] -= 1

min1 = min(cnt_change_to_b)
min2 = min(cnt_change_to_w)
print(min(min1, min2))

Submission status: Accepted

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

tmp = [0 for _ in range(N+1)]

#if S[0] == '.':
   # tmp[0] = 1

for i in range(N):
    if S[i] == '.':
        tmp[i+1] = tmp[i] + 1
    else:
        tmp[i+1] = tmp[i]
  
res1 = 10 ** 9
for i in range(N):
    res1 = min((i+1) - tmp[i+1] + tmp[N] - tmp[i+1], res1)
        
b = 0
w = 0
for i in range(N):
    if S[i] == '#':
        b += 1
    else:
        w += 1

res3 = N - max(b, w)

print(min(res1, res3))

Submission status: Accepted

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

def run(N, S):
    num_black= S.count('#')

    arr = []
    nSharp = 0
    nDot = 0
    flagDot = False
    if S[0] == '.':
        flagDot = True
    for i in S:
        if i == '#':
            if flagDot:
                arr.append((nSharp, nDot))
                flagDot = False
                nSharp = 0
                nDot = 0
            nSharp += 1
        else:
            flagDot = True
            nDot += 1
    arr.append((nSharp, nDot))    

    result = N - num_black
    min_result = result
    for i,val in enumerate(arr):
        result += val[0] - val[1]
        min_result = min(result, min_result)
        
    return min_result
        
print(run(N, S))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
whi=0
bla=0
c1=0
dp=[[0,0] for i in range(N+1)]
for i in range(N):
    s=S[i]
    if s=="#":
        dp[i+1][0]=dp[i][0]+1
    else:
        dp[i+1][0]=dp[i][0]
for i in range(N):
    s=S[N-1-i]
    if s==".":
        dp[N-i-1][1]=dp[N-i][1]+1
    else:
        dp[N-i-1][1]=dp[N-i][1]


ans=float("inf")
for i in range(N+1):
    ans=min(ans,dp[i][0]+dp[i][1])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
l = len(s)
mincnt = n
nums = [[0, 0]]
if s[0] == ".":
    nums[0][0] = 1
else:
    nums[0][1] = 1
if l == 1:
    print(0)
    exit()

for c in s[1:]:
    last = nums[-1]
    nums.append([last[0] + 1, last[1]] if c == "." else [last[0], last[1] + 1])

for i in range(0, l):
    b_before = nums[i][1] - (1 if s[i] == "#" else 0)
    w_after = nums[-1][0] - nums[i][0] + (1 if s[i] == "." else 0)
    mincnt = min(mincnt, b_before + w_after)
mincnt = min(mincnt, nums[-1][1])
print(mincnt)

Submission status: Accepted

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

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

wc = S.count('.')
bc = 0
ans = wc + bc
for s in S:
    if s == '.':
        wc -= 1
    else:
        bc += 1
    temp = wc + bc
    ans = min(temp, ans)
        
print(ans)

Submission status: Accepted

Solution code:

import numpy as np

N = int(input())
s = input()

S = []
for c in s:
    S.append(c)
    
A = np.zeros(N+1)
if S[0] == "#":
    A[0] = 0 
for i in range(1,N+1):
    if S[i-1] == "#":
        A[i] = A[i-1] + 1
    else:
        A[i] = A[i-1]
    
minimum = N
for i in range(N+1):
    num = int(A[i] + (N-i-(A[N]-A[i])))
    if minimum > num:
        minimum = num
print(minimum)

Submission status: Accepted

Solution code:
import numpy as np

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

black_stones = []
white_stones = []

black_stone_counter = 0
for stone_color in S:
    if stone_color == "#":
        black_stone_counter += 1
    black_stones.append(black_stone_counter)

white_stone_counter = 0
for stone_color in S[::-1]:
    if stone_color == ".":
        white_stone_counter += 1
    white_stones.append(white_stone_counter)

black_stones_np = np.array(black_stones)
white_stones.reverse()
white_stones_np = np.array(white_stones)

sum_stones_np = black_stones_np + white_stones_np

print(sum_stones_np.min()-1)

Submission status: Accepted

Solution code:
import sys
import collections

def solve():
    N=int(sys.stdin.readline().rstrip())
    S=list(sys.stdin.readline().rstrip())
    whites=[0]*(N+1)
    blacks=[0]*(N+1)
    for i,c in enumerate(S):
        if c=='.':
            whites[i+1]=whites[i]+1
            blacks[i+1]=blacks[i]
        else:
            whites[i+1]=whites[i]
            blacks[i+1]=blacks[i]+1

    # 左からi番目から左を白に、右を黒にする
    inf=1<<60
    ans=inf
    #print(whites)
    #print(blacks)
    all_whites=whites[N]
    for i in range(N+1):
        ans1=blacks[i] + (all_whites-whites[i])
        #print(ans1)
        ans=min(ans,ans1)
    return ans

print(solve())

Submission status: Accepted

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

wcs, bcs = [0], [0]
wc, bc = 0, 0
if s[0] == '#':
  bc = 1
for prevs, _s in zip(s, s[1:]):
  if prevs != _s:
    bcs.append(bc + bcs[-1])
    if _s == '#':
      bc = 1
    else:
      bc = 0
  else:
    if _s == '#':
      bc += 1
bcs.append(bc + bcs[-1])

wc, bc = 0, 0
if s[-1] == '.':
  wc = 1
for prevs, _s in zip(s[::-1], s[::-1][1:]):
  if prevs != _s:
    wcs.append(wc + wcs[-1])
    if _s == '.':
      wc = 1
    else:
      wc = 0
  else:
    if _s == '.':
      wc += 1
wcs.append(wc + wcs[-1])

minbw = pow(10, 6)
for bc, wc in zip(bcs, wcs[::-1]):
  if bc + wc < minbw:
    minbw = bc + wc
print(minbw)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
sb=[0]*n
sw=[0]*n
wb=[]
for i in range(n-1):
    if s[i:i+2]==".#":
        wb.append(i)
for i in range(n):
    if s[i]==".":
        if i==0:
            sw[i]=1
        else:
            sw[i]=1+sw[i-1]
            sb[i]=sb[i-1]
    else:
        if i==0:
            sb[i]=1
        else:
            sb[i]=1+sb[i-1]
            sw[i]=sw[i-1]
anses=[len([x for x in s if x=="#"]),len([x for x in s if x=="."])]
for i in wb:
    anses.append(sb[i]+sw[n-1]-sw[i])
print(min(anses))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
cur=0
lis=["" for i in range(N)]
lis[cur]=S[0]
for c in S[1:]:
	ss=lis[cur]
	if c==".":
		lis[cur]=ss+"."
	else:
		if ss[-1]=="#":
			lis[cur]=ss+"#"
		else:
			cur+=1
			lis[cur]="#"
def counting(sss):
	curb=sss.find("#")
	curw=sss.rfind(".")
	return tuple([sss[:curw+1].count("#"),sss[curb:].count(".")])

c=0
lasc=0
kugi=[]
for l in lis:
	if l=="":
		break
	else:
		ka=counting(l)
		c+=ka[0]
		kugi.append(ka)
lasc=c
for w,b in kugi[::-1]:
	c=c-w+b
	if c<lasc:
		lasc=c
print(lasc)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
# . = しろ
# # = 黒
# #の横に.がないようにしたい
# #の横に.があったら#を.に変える
# or #の横に.があったら.を#に変える

# when do you replace now char to .
# 

# テストケース
"""
3
#..

3
##.
"""
# => .....# = 2

def inorderReplace(S , N): 
    S = list(S)
    cnt = 0
    for i in range(N - 1) : 
        nowChar = S[i]
        nextChar = S[i + 1]
        if nowChar == "#" and nextChar == "." : 
            cnt += 1
            S[i + 1] = "#"
    return cnt

def calcCount(S , N) : 
    countingChar = S[0]
    rst = []
    count = 1
    for s in S[1:] :
        if countingChar == s : 
            count += 1
        else : 
            rst.append((countingChar , count))
            count = 1
            countingChar = s
    rst.append((countingChar , count))
    return rst

def countRightChange(countingList) : 
    #全部を.に変えるコスト
    cnt = 0
    for elem in countingList : 
        if elem[0] == "#" : 
            cnt += elem[1]
    return cnt

def countLeftChange(countingList) : 
    # 全部を#に変えるコスト
    cnt = 0
    for elem in countingList : 
        if elem[0] == "." : 
            cnt += elem[1]
    return cnt

def calcPoint(countingList) : 
    a = 0
    b = countLeftChange(countingList)
    minVal = a + b
    for i in range(len(countingList)) : 
        elem = countingList[i]
        if elem[0] == "." : 
            a += 0
            b -= elem[1]
        elif elem[0] == "#" : 
            a += elem[1]
            b -= 0
        if minVal > a + b : 
            minVal = a + b
    return minVal

countingList = calcCount(S , N)
cnt2 = calcPoint(countingList)

print(cnt2)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
N=int(stdin.readline().rstrip())
S=(stdin.readline().rstrip())
A=[0]*N ## .
B=[0]*N ## #
a_count=0
b_count=0

for ind,i in enumerate(list(S)):
    if i == ".":
        a_count+=1
        A[ind] = a_count
        B[ind] = b_count
    else:
        b_count+=1
        B[ind] = b_count
        A[ind] = a_count
A.insert(0,0)
B.insert(0,0)
dif=np.array(A) - np.array(B)
dif_ind = np.argmax(dif)
ans=B[dif_ind] + A[-1] - A[dif_ind]
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = list(input())
    
    arr = []
    cnt = 1
    for i in range(1, n):
        if s[i] == s[i - 1]:
            cnt += 1
        else:
            arr.append(cnt)
            cnt = 1
    arr.append(cnt)
    
    if s[0] == '.':
        arr = [0] + arr
    if s[-1] == '#':
        arr += [0]
    
    for i in range(len(arr) - 3, -1, -2):
        arr[i] += arr[i + 2]
    for i in range(2, len(arr), 2):
        arr[i] += arr[i - 2]
    
    arr += [0, 0]
    
    ans = arr[1]
    for i in range(1, len(arr) - 2, 2):
        ans = min(ans, arr[i - 1] + arr[i + 2])
    
    print(ans)
    return 0

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9+7

n = int(input())
S = input()
W = [0]*(2*10**5+1)
B = [0]*(2*10**5+1)
for i in range(n):
    if S[i] == '.':
        W[i] = 1
    else:
        B[i] = 1
for i in range(1,2*10**5+1):
    W[i] += W[i-1]
    B[i] += B[i-1]
W = [0] + W
B = [0] + B
res = INF
for i in range(2*10**5+1):
    ans = W[-1]-W[i]+B[i]
    if ans <= res:
        res = ans
print(res)

Submission status: Accepted

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

l_count = 0
r_count = sum([1 for c in S if c == "."])
count_if_contain_black = l_count+r_count
count_if_all_white = 0
for c in S:
    if c == "#":
        l_count += 1
        count_if_all_white += 1
    else:
        r_count -= 1
        
    count_if_contain_black = min(count_if_contain_black, l_count+r_count)

print(min(count_if_all_white, count_if_contain_black))

Submission status: Accepted

Solution code:
import numpy as np
  
input()
S = np.asarray(list(str(input())))

rw = S[S=="."].size
rb = S[S=="#"].size
lw = 0
lb = 0
res = lb + rw
for s in S:
 if s == "#":
  rb -= 1
  lb += 1
 else:
  rw -= 1
  lw += 1
 res = min(res,lb+rw)
print(res)

Submission status: Accepted

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

from sys import stdin
    
def calc(n, s):
    s2 = [ c == '#' for c in s]
    total = sum(s2)
    _min = min(total, n-total)
    tr = 0
    for i,c in enumerate(s2):
        if c:
            tr += 1
        op = 2*tr+n-(i+1)-total
        if op < _min:
            _min = op

    return _min

def main():
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    ans = calc(n, s)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

c = [0]
cc = [0]
for i in range(n):
  if s[i] == ".":
    c.append(c[-1]+1)
    cc.append(cc[-1])
  else:
    c.append(c[-1])
    cc.append(cc[-1]+1)
c = c[1:]
cc = cc[1:]

ans = min(c[-1], cc[-1])
for i in range(n):
  ans = min(ans, cc[i]+c[-1]-c[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input()) 
S = input() 
 
#.......######
# a[n] = n個目より左にある#の数
# b[n] = n個目より右にある.の数
 
a = [0] * (N+2)
b = [0] * (N+2)
 
cnt = 2
for x in S:
    if x == "#":
        a[cnt] = a[cnt-1] + 1
    else:
        a[cnt] = a[cnt-1] 
    cnt += 1
 
cnt =N
Sinv = S[::-1]
for x in Sinv:
    if x == ".":
        b[cnt] = b[cnt+1] + 1
    else:
        b[cnt] = b[cnt+1] 
    cnt -= 1
 
 
 
c = []
 
for index in range(N+2):
    c.append(a[index] + b[index])
c[0] = 999999
 
print(min(c))

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
S = input()
black = [int(s=="#") for s in S]
white = [int(s==".") for s in S[::-1]]

a_black = [0]+list(accumulate(black))
a_white = list(accumulate(white))[::-1]+[0]

ans = 1000000
for b,w in zip(a_black,a_white):
    ans = min(ans, b+w)
print(ans)

Submission status: Accepted

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

i = 0
while i<len(s) and s[i] == '.':
  i+=1
j = n-1
while j>=0 and s[j] == '#':
  j-=1

s = s[i:j+1]
r = min(s.count('#'), s.count('.'))

w = s.count('.')
b = 0
c = 0
for i in range(len(s)):
  if s[i] == '#':
    b += 1
  else:
    w -= 1
  r = min(r, w+b)

print(r)

Submission status: Accepted

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

count_if_all_white = 0
for c in S:
    if c == "#":
        count_if_all_white += 1

l_count = 0
r_count = sum([1 for c in S if c == "."])
count_if_contain_black = l_count+r_count
for c in S:
    if c == "#":
        l_count += 1
    else:
        r_count -= 1
        
    count_if_contain_black = min(count_if_contain_black, l_count+r_count)

print(min(count_if_all_white, count_if_contain_black))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
la=[0]
lb=[0]
for i in s:
    if i==".":
        la.append(la[-1]+1)
        lb.append(lb[-1])
    if i=="#":
        la.append(la[-1])
        lb.append(lb[-1]+1)

ans=1000000000000
for i in range(n+1):
    ans=min(ans,lb[i]-lb[0]+la[-1]-la[i])
print(ans)

Submission status: Accepted

Solution code:
def minToggle(arr, n): 
  
    zero =[0 for i in range(n + 1+1)] 
    zero[0] = 0
   
    # Fill entries in zero[] 
    # such that zero[i] 
    # stores count of zeroes 
    # to the left of i 
    # (exl 
    for i in range(1, n + 1): 
      
        # If zero found 
        # update zero[] array 
        if (arr[i-1] == 0): 
            zero[i] = zero[i-1] + 1
        else: 
            zero[i] = zero[i-1] 
   
    # Finding the minimum 
    # toggle required from 
    # every index(0 to n-1) 
    ans = n 
    for i in range(1, n + 1): 
        ans = min(ans, i - zero[i] + zero[n] - zero[i]) 
   
    return ans 
      
# Driver Program 
n=int(input())
s=input().rstrip()
arr=[]
ansi=min(s.count('.'),s.count('#'))
for i in s:
    if i=='.':
        arr.append(0)
    else:
        arr.append(1)
n = len(arr) 
  
p=minToggle(arr, n)
ansi=min(ansi,p)
print(ansi)
  
# This code is contributed 
# by Anant Agarwal.

Submission status: Accepted

Solution code:
N = int(input())
S = str(input())
white_count = 0
black_count = 0
count = 0
white = []
black = []
for i in range(N):
    if S[i] == ".":
        white_count += 1
    else:
        black_count += 1
    white.append(white_count)
    black.append(black_count)

ans = []
for i in range(N):
    ans.append(white_count-white[i]+black[i])
ans_min = min(ans)

print(min(white_count,black_count,ans_min))

Submission status: Accepted

Solution code:
n=int(input())
S=input()
sflag=0
a=0
b=0
c1=0
c2=0

d=0
for i in S:
    if i==".":
        a+=1
    if i=="#":
        b+=1
out=min(a,b)
siro=0
kuro=0
for i in S:
    if i==".":
        siro+=1
        a-=1
    else:
        kuro+=1
        b-=1
    if kuro+a < out:
        out=kuro+a
    #print(kuro+a)
print(out)

Submission status: Accepted

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

b = [0]*(N+1)
w = [0]*(N+1)

for i,s in enumerate(S):
    b[i+1] = b[i]
    if s == "#":
        b[i+1] += 1

for i,s in enumerate(S[::-1]):
    w[i+1] = w[i]
    if s == ".":
        w[i+1] += 1

w.reverse()

ans = float('inf')

for B,W in zip(b,w):
    if ans > B+W:
        ans = B+W
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
count = 0
for s in S:
    if s == ".":
        count += 1
left = 0
right = count
minimum = left+right
for n in range(N):
    if S[n] == "#":
        left += 1
    else:
        right -= 1
    if left+right < minimum:
        minimum = left+right
print(minimum)

Submission status: Accepted

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

left = S[:0].count('#')
right = S[0:].count('.')
cou = left+right

for i in range(1,N+1):
    if S[i-1]=='#':
        left+=1
    else:
        right-=1
    cou = min(cou,left+right)
print(cou)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
s = input()[:-1]
to_w = 0
to_b = 0
to_w_list = []
to_b_list = []
for i in range(n):
    if s[i] == '#':
        to_w += 1
    if s[-i-1] == '.':
        to_b += 1
    to_w_list.append(to_w)
    to_b_list.append(to_b)
to_b_list.reverse()
ans = min(to_w_list[-1], to_b_list[0])
for i in range(n-1):
    ans = min(ans, to_w_list[i]+to_b_list[i+1])
print(ans)

Submission status: Accepted

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

cum = [0]*(N+1)
for i in range(N):
  if S[i] == '#':
    cum[i+1] = cum[i]+1
  else:
    cum[i+1] = cum[i]
ans = [0]*(N+1)
for i in range(N+1):
  ans[i] = cum[i] + ((N-i)-(cum[N]-cum[i]))
print(min(ans))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
b = 0
w = 0
for i in range(n):
    if s[i] == '.':
        b = min(b,w) + 1
    else:
        b = min(b, w)
        w += 1
print(min(b, w))

Submission status: Accepted

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

#0：まだ.　1：もう#
dp = [[0, 0] for _ in range(n+1)]

for i in range(n):
  if S[i] == '.':
    dp[i+1][0] = dp[i][0]
    dp[i+1][1] = min(dp[i][0], dp[i][1])+1
  else:
    dp[i+1][0] = dp[i][0]+1
    dp[i+1][1] = min(dp[i][0], dp[i][1])
    
#print(dp)
print(min(dp[n]))

Submission status: Accepted

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

dp=[0]*(n+1)
for i in range(n):
  if s[i]=="#":
    dp[0]+=1

for i in range(n):
  if s[n-i-1]=="#":
    dp[i+1]=dp[i]-1
  else:
    dp[i+1]=dp[i]+1

print(min(dp))

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
d = [0]*n
p = [0]*n
for i in range(n):
    if i > 0:
        d[i] = d[i-1]
    if s[i] != '.':
        d[i] += 1
for i in range(n-1, -1, -1):
    if i < (n-1):
        p[i] = p[i+1]
    if s[i] != '#':
        p[i] += 1

d = [0]+d
p = p+[0]
ans = 2**32
for i in range(n+1):
    t = d[i]+p[i]
    if t < ans:
        ans = t
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
tmp=1
L=[]
ans=10**6
black=0
white=0
for i in range(1,len(S)):
    if S[i]==S[i-1]:
        tmp+=1
    else:
        L.append(tmp)
        tmp=1
    if i ==len(S)-1:
        L.append(tmp)

    if S[i]=='#':
        black+=1
    else:
        white+=1

cul=[0]*(len(L)+2)
for i in range(len(L)):
    cul[i+2]=L[i]+cul[i]


if S[0]=='.':
    white+=1
    for i in range(2,len(cul)):
        if i%2==0:
            ans=min(ans,cul[i-1]+white-cul[i])
        else:
            ans=min(ans,cul[i]+white-cul[i-1])
else:
    black+=1
    for i in range(2,len(cul)):
        if i % 2 == 0:
            ans = min(ans,cul[i]+white-cul[i-1])
        else:
            ans = min(ans,cul[i-1]+white-cul[i])


if len(L)==1:
    ans=0
else:
    ans=min(ans,sum(L[0::2]),sum(L[1::2]))

print(ans)

Submission status: Accepted

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

w = [0] * N
b = [0] * N

if S[0] == '#':
    w[0] = 1
for i in range(1, N):
    if S[i] == '#':
        w[i] = w[i-1] + 1
    else:
        w[i] = w[i-1]

if S[N-1] == '.':
    b[N-1] = 1
for i in range(N-2, -1, -1):
    if S[i] == '.':
        b[i] = b[i+1] + 1
    else:
        b[i] = b[i+1]

m = min(b[0], w[N-1])
for n in range(N-1):
    v = w[n] + b[n+1]
    if v < m:
        m = v
print(m)

Submission status: Accepted

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

sum_w = [0]
sum_b = [0]
for i in range(N):
  if S[i] == ".":
    sum_w.append(sum_w[-1] + 1)
    sum_b.append(sum_b[-1])
  else:
    sum_b.append(sum_b[-1] + 1)
    sum_w.append(sum_w[-1])

ans = float("inf")
for i in range(N + 1):
  ans = min(ans, sum_b[i] + sum_w[-1] - sum_w[i])
  
print(ans)

Submission status: Accepted

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

def black():
    result = [0] * n
    count = 0
    for i in range(n):
        if s[-i-1] == '.':
            count += 1
        result[-i-1] = count
    return result + [0]

def white():
    result = [0] * n
    count = 0
    for i in range(n):
        if s[i] == '#':
            count += 1
        result[i] = count
    return [0] + result

num = [x + y for x,y in zip(black(), white())]
result = min(num)

print(result)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
ans = 10**8
li = [0]

b=[0]
w=[0]
for ind,i in enumerate(S):
    if(ind==0):
        if(i=='#'):
            b+=[0]
            b[-1]+=1
        else:
            w[-1]+=1
    elif(ind==N-1):
        if(i==S[ind-1]):
            if(i=='#'):
                b[-1]+=1
            else:
                w[-1]+=1
                b+=[b[-1]]
        else:
            if(i=='#'):
                b+=[b[-1]+1]
            else:
                w+=[w[-1]+1]
                b+=[b[-1]]

    else:
        if(i==S[ind-1]):
            if(i=='#'):
                b[-1]+=1
            else:
                w[-1]+=1
        else:
            if(i=='#'):
                b+=[b[-1]+1]
            else:
                w+=[w[-1]+1]
b = [0]+b
w = [0]+w
for ind,i in enumerate(w):
    ans = min(ans,w[-1]-w[ind]+b[ind])



print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
t = S.count(".")
if t == N or t == 0:
    print(0)
    exit(0)

W = [0 for k in range(N+1)]
B = [0 for k in range(N+1)]

for k in range(N):
    if S[k] == "#":
        B[k] = B[k-1] + 1
    else:
        B[k] = B[k-1]

W[0] = t
for k in range(N):
    if S[k] == ".":
        W[k+1] = W[k] - 1
    else:
        W[k+1] = W[k]
ans = N
for k in range(N):
    ans = min(ans,W[k+1]+B[k])
print(min(ans,t,S.count("#")))

Submission status: Accepted

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

#違反している黒と白の数数えて
#少ない方で置き換える

answer = 0

#まず一番左の黒のいちを見つける
left_black = -1
right_white = -1

for i in range(N):
    if S[i]=='#':
        if S.count('#')==N-i:
            break
        left_black = i
        break

for i in reversed(range(N)):
    if S[i]=='.':
        right_white = i
        break

# print(right_white)



# print(left_black)
#left_blackが-1かN-1なら自動的に0


if left_black!=-1 and left_black!=N-1:
    S2 = S[left_black:right_white+1]
    length = len(S2)
    #どこまで全て白で塗るか決める
    white_black_sa = [0]*length
    if S2[0]=='.':
        white_black_sa[0] = 1
    else:
        white_black_sa[0] = -1

    for i in range(1,length):
        if S2[i]=='.':
            white_black_sa[i]=white_black_sa[i-1]+1
        else:
            white_black_sa[i]=white_black_sa[i-1]-1
    
    sa_max_idx = white_black_sa.index(max(white_black_sa))
    # print(S2)
    # print(S2[:sa_max_idx])
    # print(S2[sa_max_idx+1:])
    black_disc = S2[:sa_max_idx].count('#')
    white_disc = S2[sa_max_idx+1:].count('.')
    # print(white_black_sa)
    # print(white_disc,black_disc)
    answer = black_disc + white_disc





print(answer)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Min = N
siro = S.count(".")
kuro = S.count("#")
Min = min([siro, kuro])
siro_now = 0
for i in range(N):
    if S[i] == ".":
        siro_now += 1
    cnt = (((i+1)-siro_now) + (siro - siro_now))
    if Min > cnt:
        Min = cnt
print(Min)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
s = input()
num = []
bl = 0
wh = 0
for i in range(n):
    if s[i] == "#":
        num.append([i,wh])
        bl += 1
    else:
        wh += 1
min = n
if len(num) > 0:
    for i in range(len(num)):
        temp = (num[i][0] - num[i][1]) + (n - bl - num[i][1])
        if temp < min:
            min = temp
    if min > bl:
        min = bl
    print(min)
else:
    print("0")

Submission status: Accepted

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

all = 0
tmp = 0
for i in S:
    if  i == '.':
        all += 1
ans = all
for i in range(N):
    if S[i] == '.':
        tmp += 1
    ans = min(ans, all - tmp + i + 1 - tmp)

print ans

Submission status: Accepted

Solution code:
N = int(input())
S = input()
first_black = 0
count = 0
for i in range (N):
    if first_black == 0 and S[i]=='#':
        first_black = 1
    if first_black == 1 and S[i]== '.':
        count +=1
        
first_white = 0
white_count = 0
for i in range (N):
    if first_white == 0 and S[N-i-1]=='.':
        first_white = 1
    if first_white == 1 and S[N-i-1]== '#':
        white_count +=1

white_black = 10**6

black_count_left = 0
white_count_right = S.count('.')
ans = black_count_left + white_count_right

for i in range (N):
    if S[i] == '#':
        black_count_left+=1
    elif S[i] == '.':
        white_count_right-=1
    if ans >= black_count_left+white_count_right:
        ans = black_count_left+white_count_right
        
print(min(count,white_count, ans))

Submission status: Accepted

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

b=0
w=S.count(".")

ans=b+w

for s in S:
	if s == "#":
		b += 1
	else:
		w -= 1
	ans=min(ans, b+w)

print(ans)