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: Time Limit Exceeded

Solution code:

N = int(input())
S0 = input()
S = [S0[i] for i in range(N)]
minimum = N + 1

for i in range(N+1):
    T = ['.' for j in range(i)] + ['#' for j in range(N-i)]
    m = 0
    for k in range(N):
        if S[k] != T[k]:
            m += 1
    if m < minimum:
        minimum = m

print(minimum)

Submission status: Time Limit Exceeded

Solution code:
_ = input()
S = input().strip()

min_s = len(S)
for d in range(len(S)+1):
  left = len([1 for s in S[:d] if s == '#'])
  right = len([1 for s in S[d:] if s == '.'])
  if min_s > left+right:
    min_s = left+right

print(min_s)

Submission status: Time Limit Exceeded

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

s_bin = '0b' + s.replace('.', '0').replace('#', '1')
min_cost = n

for i in range(n+1):
    cand_s_bin = '0b' + ('0' * i) + ('1' * (n-i))
    diff = bin(int(s_bin, 2) ^ int(cand_s_bin, 2))
    cost = diff.count('1')
    if cost < min_cost:
        min_cost = cost

print(min_cost)

Submission status: Time Limit Exceeded

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

#最終的な白の数は0からN
#白が左からt個、以降黒がT-t個
R=[]
for i in range(N+1):
  R.append(S[0:i].count('#')+S[i:N].count('.'))
print(min(R))

Submission status: Time Limit Exceeded

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

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

needs = [n]
cnt = 0
for i in range(n):
    if s[i] == "#":
        need = 0
        cnt += 1
        for j in range(i,n):
            if s[j] == ".":
                need += 1
        needs.append(need + cnt - 1)
need = min(needs)

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

print(min(black,need))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
N = int(input())
S = input()
ans = 1000000
for i in range(N+1):
    l = S[:i]
    r = S[i:]
    #print (l,r)
    cnt = l.count("#")+r.count(".")
    #print (cnt)
    if cnt < ans:
        ans = cnt
print (ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=0
while s.find("#.")!=-1:
    ans+=1
    tmp=s.find("#.")+1
    s=s[:tmp]+"#"+s[tmp+1:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
r = min(s.count('#'), s.count('.'))
for i in range(n-1):
  r = min(r, s[:i+1].count('#') + s[i+1:].count('.')) 
print(r)

Submission status: Time Limit Exceeded

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

ans = 10 ** 6
for i in range(1,n):
    ans = min(ans, s[:i].count("#") + s[i:].count("."))

ans = min(ans, s.count("#"), s.count("."))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_c

N = int(input())
S = str(input())
Sarray = list(S)
Sarraynum = []

#白0
for i in range(len(Sarray)):
    if Sarray[i] == '.':
        Sarraynum.append(0)
    else:
        Sarraynum.append(1)

white2black = len(Sarraynum)
black2white = len(Sarraynum)
for i in range(len(Sarraynum)):
    black2whiteTMP = 0
    white2blackTMP = len(Sarraynum) - i - 1
    for j in range(i):
        black2whiteTMP += Sarraynum[j]
    for j in range(i + 1, len(Sarraynum)):
            white2blackTMP -= Sarraynum[j]
    if black2whiteTMP + white2blackTMP < white2black + black2white:
        white2black = white2blackTMP
        black2white = black2whiteTMP


print(white2black + black2white)

Submission status: Time Limit Exceeded

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

import numpy as np
arr = np.empty(N+1,dtype='object')

for i in range(len(arr)):
    arr[i] ='.'*i+  '#'*(N-i)

countlist = []
for i in range(len(arr)):
    s = arr[i]
    length = len(s)
    c = 0
    for j in range(length):
        if s[j] != S[j]:
            c += 1
    countlist.append(c)

print(min(countlist))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
N = int(input())
S = input()

min = N
tmp = 0
if S.count('#') == N or S.count('.') == N:
    print(0)
else:
    for n in range(N):
        tmp = S[:n].count('#') + S[n:].count('.')
        if tmp < min:
            min = tmp
    print(min)

Submission status: Time Limit Exceeded

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

black = 0
black_counts = []
white = 0
white_counts = []
for i in range(N):
    if S[i] == '#':
        black += 1
    black_counts.append(black)

    if S[-1-i] == '.':
        white += 1
    white_counts.insert(0, white)

min_count = min(black_counts[N-1], white_counts[0])
for i in range(N-1):
    min_count = min(min_count, black_counts[i] + white_counts[i+1])
print(min_count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
ans=0
while s.find("#.")!=-1:
    ans+=1
    tmp=s.find("#.")+1
    s=list(s)
    s[tmp]="#"
    s="".join(s)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=input()
#A,B,C=map(int,input().split())
#A=list(map(int,input().split()))
T=""
whi=0
bla=0
S_=""
c1=0
for i in S:
    if i=="#":
        break
    c1+=1
for i in S:
    T=i+T
    if i==".":
        whi+=1
    else:
        bla+=1
c2=0
for i in T:
    if i==".":
        break
    c2+=1
"""
print(whi)
print(bla)
print(c1)
print(c2)
print(T)
"""
print(min(whi-c1,bla-c2))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N-1):
    if S[i] == '#' and S[i+1] == '.':
        tmp_S = list(S)
        tmp_S[i+1] = '#'
        S = "".join(tmp_S)
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
ans = len(s)
if min(s.count("#"),s.count("."))==0:
     ans = 0
else:
     for i in range(n):
          ans = min(ans,s[:i].count("#")+s[i:].count("."))

print(ans)

Submission status: Time Limit Exceeded

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

res = float("inf")

if "." not in S or "#" not in S:
    res = 0

for i in range(N):
    res = min(res, S[:i].count("#") + S[i:].count("."))

print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
init = True
m = s.count('#')
l = [0] * m
idx = 0
for i in range(n):
    if s[i] == '#':
        l[idx] = i
        idx += 1
ans = m
for i in range(m):
    ans = min(ans, i + (n - l[i] - 1 - (m - i - 1)))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
tmp=s.count('.')
ans=tmp
for i in range(n):
  if s[i]=='.':
    tmp-=1
  else:
    tmp+=1
  ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
wcount = 0
min_val = 0
for i in range(n):
    if s[i] == '.':
        wcount += 1
    min_val = min(min_val, i + 1 - wcount * 2)
print(wcount + min_val)

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    S = input()

    # '#.'という箇所が1箇所でもあるとダメなので、ある場所に黒が現れたら
    # 、そこから右は全て黒にならないといけない

    Wt = [0] * (N + 1)
    Bl = [0] * (N + 1)

    for i in range(N):
        if S[i] == "#":
            Bl[i + 1] = Bl[i] + 1
            Wt[i + 1] = Wt[i]
        else:
            Wt[i + 1] = Wt[i] + 1
            Bl[i + 1] = Bl[i]

    ans = 1 << 60
    for i in range(N + 1):
        tmp = 0
        # left を全部白に
        tmp += Bl[i] - Bl[0]

        # right を全部黒に
        tmp += Wt[N] - Wt[i]

        ans = min(ans, tmp)

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline
N = int(input())
S = list(input().strip())
counter = Counter(S)
if len(counter) == 1:
    print(0)
else:
    ans = min(counter["."], counter["#"])
    # 操作後：境界に対して左は白、右は黒になる
    # 境界をどこにするかを全探索
    white = counter["."]
    black = counter["#"]
    left_w = 0
    left_b = 0
    for i in range(N):
        if S[i] == ".":
            left_w += 1
        else:
            left_b += 1
        ans = min(ans, left_b + white - left_w)
    
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cw = 0
cb = 0
di = []
a = -1
b = 0
mn = float("inf")
for i in range(n):
    if s[i] == ".":
        cw += 1
    else:
        di.append(i)
        cb += 1
for k in range(len(di)):
    if mn > cw - di[k] + 2*k:
        mn = cw - di[k] + 2*k
print(min(min(cw,cb),mn))

Submission status: Accepted

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

black = []
white = []

cb=0
cw=0
for l in s:
    if l =="#":
        cb+=1
    else:
        cw+=1
    black.append(cb)
    white.append(cw)

if n == 1:
    print(0)
else:
    ans = [white[-1],black[-1]]
    for i in range(n):
        ans.append(black[i-1]+white[-1]-white[i-1])
    print(min(ans))

Submission status: Accepted

Solution code:
# author:  Taichicchi
# created: 26.09.2020 14:35:45

import sys

N = int(input())

S = input()

ls_l = [0]
ls_r = [0]

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

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

ls_r.reverse()

# print(ls_l)
# print(ls_r)

ans = 10 ** 6

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n=I()
    s=SI()
    B=0
    W=0
    for i in range(n):
        if s[i]=="#":
            B+=1
        else:
            W+=1
    b=0
    w=0
    ans=min(B,W)
    for i in range(n):
        if s[i]==".":
            w+=1
            ans=min(ans,b+W-w)
        else:
            b+=1
    print(ans)
        
        







if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
a = 0
b = S.count('.')
num = min(N - b, b)
for i in range(N):
  x = S[i] =='#'
  a += x
  b -= 1-x
  num = min(num, a+b)
print(num)

Submission status: Accepted

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

# 左側の黒の個数, 右側の白の個数
b, w = 0, s.count('.')
ans = min(s.count('#'), w)
for i in range(n):
    if s[i] == '#':
        b += 1
    elif s[i] == '.':
        w -= 1
    ans = min(ans, b+w)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
m = 10 ** 6
tot1 = 0
cnt1 = 0
cnt0 = 0
for s in S:
    if(s == '#'):
        cnt0 += 1
    else:
        cnt1 += 1
        tot1 += 1
    m = min(m,cnt0-cnt1)
m += tot1
m = min(m,tot1)
print(m)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
w_right=s.count(".")
b_left=0
ans=w_right
for i in range(n):
  if s[i]=="#":
    b_left+=1
  else:
    w_right-=1
  ans=min(ans,w_right+b_left)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
dp=[0]*(n+1)

for i in range(1,n+1):
  if s[i-1]==".":
    cnt=0
  else:
    cnt=1
  dp[i]=dp[i-1]+cnt
ans=n
for i in range(n+1):
  ans=min(ans,dp[i]+(n-i)-(dp[n]-dp[i]))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Black = [0]*(N+1)
White = [S.count('.')]*(N+1)
DispS = [S.count('.')]*(N+1)
for TN in range(0,N):
    Black[TN+1] = Black[TN]+[0,1][S[TN]=='#']
    White[TN+1] = White[TN]-[0,1][S[TN]=='.']
    DispS[TN+1] = Black[TN+1]+White[TN+1]
print(min(DispS))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=s.count('.')
cnt=ans

for i in s:
    if i=='.':
        cnt-=1
        ans=min(ans,cnt)
    
    else:
        cnt+=1

ans=min(ans,cnt)


print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
x = 0
y = s.count('.')
c = min(n-y, y)
for i in range(n):
    t = s[i] == '#' #＃であればｔがTrueになる
    x += t
    y -= 1 - t
    c = min(c, x+y)
print(c)

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,input().replace('#','1').replace('.','0')))
 
cum=[0]
for i in range(N):
  cum.append(cum[-1]+S[i])
  
ans=10**20
for i in range(N+1):
  b = cum[i]
  w = N-i-(cum[-1]-cum[i])
  ans = min(ans,b+w)
  
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
A = []
for si in s:
  if si == "#":
    A.append(1)
  else:
    A.append(0)
for i in range(1, len(A)):
  A[i] += A[i-1]

ans = n - A[n-1]
for i in range(n):
  b2w = A[i]
  w2b = n - i - 1 - (A[n-1] - A[i])
  if ans > b2w + w2b:
    ans = b2w + w2b

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
x = 0
y = S.count('.')
c = min(n-y, y)
for i in range(n):
  t = S[i]=='#'
  x += t
  y -= 1-t
  c = min(c, x+y)
print(c)

Submission status: Accepted

Solution code:
_ = input()
S = input().lstrip('.').rstrip('#')
n = len(S)

x = 0
y = S.count('.')
c = min(n-y, y)
for i in range(n):
  t = S[i]=='#'
  x += t
  y -= 1-t
  c = min(c, x+y)
print(c)

Submission status: Accepted

Solution code:
_ = input()
S = input().lstrip('.').rstrip('#')
n = len(S)

x = 0
y = S.count('.')
c = min(n-y, y)
for i in range(n):
  if S[i] == '#':
    x += 1
  else:
    y -= 1
  c = min(c, x+y)
print(c)

Submission status: Accepted

Solution code:
_ = input()
S = input().lstrip('.').rstrip('#')
n = len(S)
A = list(S)

x = 0
y = S.count('.')
ans = min(n-y, y)
for i in range(n):
  if S[i] == '#':
    x += 1
  else:
    y -= 1
  ans = min(ans, x + y)
print(ans)

Submission status: Accepted

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

kuro_li = [0]*(n+1)

if s[0] == "#":
    kuro_li[1] = 1

for i in range(1,n):
    #print(i)
    kuro_li[i+1] = kuro_li[i]
    if s[i] == "#":
        kuro_li[i+1] += 1
        
siro_li = [0]*(n+1)

if s[-1] == ".":
    siro_li[-2] = 1

for i in range(n,0,-1):
    #print(i)
    siro_li[i-1] = siro_li[i]
    if s[i-1] == ".":
        siro_li[i-1] += 1
    
#print(kuro_li)
#print(siro_li)


ans = 10**10

for i in range(n+1):
    tmp = kuro_li[i] + siro_li[i]
    ans = min(ans,tmp)
    
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
ans=[]
black=0
white=0
for n in range(N):
    if S[n]=='.':
        white+=1
    else:
        black+=1
stones={'b':0,'w':white}
for n in range(N):
    if S[n]=='#':
        stones['b']+=1
    else:
        stones['w']-=1
    ans.append(stones['b']+stones['w'])
if 'b' in stones:
    if stones['b']==N:
        print(0)
    else:
        print(min(min(ans),white,black))
else:
    print(min(min(ans),white,black))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
white, black = s.count('.'), 0
ans = white+black

for i in s:
    if i == '#':
        black += 1
    else:
        white -= 1
    ans = min(ans, white+black)
print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
s=input()
acc=[0]*(n+1)
ans=n
for i in range(n):
    if s[i]=="#":
        acc[i+1]=acc[i]+1
    else:
        acc[i+1]=acc[i]
for i in range(n+1):
    w=n-i-(acc[n]-acc[i])
    b=acc[i]
    ans=min(ans,w+b)
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N,S=intput(),input()
rw=S.count('.')
lb=0
ans=rw
for i in range(N):
    if S[i]=='.':
        rw-=1
    else:
        lb+=1
    ans=min(ans,rw+lb)
print(ans)

Submission status: Accepted

Solution code:
def main():
    #input data
    import sys
    input = lambda:sys.stdin.readline().strip()
    
    N = int(input())
    S = input()
    
    #solve
    all_black = S.count('#')
    fill_one = min(N-all_black,all_black)
    b_cnt = 0

    ans = 10**10
    for i in range(N-1):
        if S[i]=='#':
            b_cnt+=1
        else:
            pass
        tmp = b_cnt+((N-i-1)-(all_black-b_cnt))
        ans = min(tmp,ans)
        # print(i,ans)

    print(min(ans,fill_one))

if __name__=='__main__':
    main()

Submission status: Accepted

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

while len(s) >= 1 and s[0] == ".":
    s = s[1:]

while len(s) >= 1 and s[-1] == "#":
    s = s[:-1]

d = []
cur = "#"
strk = 1

bl = 0
wr = 0

if len(s) > 1:
    for i in range(1, len(s)):
        if s[i] == cur:
            strk += 1
        else:
            d.append((cur, strk))
            if cur == ".":
                wr += strk

            cur = s[i]
            strk = 1

    d.append((cur, strk))
    if cur == ".":
        wr += strk

ans = wr
for i in range(len(d)):
    if d[i][0] == "#":
        bl += d[i][1]
    else:
        wr -= d[i][1]

    ans = min(ans, bl + wr)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(lambda x:1 if "#"==x else 0,list(input())))
mn=n-sum(a)
s=mn
for i in a:
  if i:
    s+=1
  else:
    s-=1
  mn=min(mn,s)
print(mn)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
right, left = 0, s.count('.')
r = [left]
for i in range(n):
    if s[i]=='#':
        right += 1
    else:
        left -= 1
    r.append(right+left)
print(min(r))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1e9)+7
INF = float('inf')


def solve():
    n = int(input())
    s = input()
    p = [0] * n
    r = [0] * n
    for i in range(n):
        if i: p[i] += p[i-1]
        if s[i] == '#': p[i] += 1
    for i in range(n-1,-1,-1):
        if i+1<n: r[i] += r[i+1]
        if s[i] == '.': r[i] += 1
    ans = min(p[-1], r[0])
    for i in range(n-1):
        ans = min(ans, p[i] + r[i + 1])
    print(ans)
    

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
1
4
-1 1 1 -1

"""

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import defaultdict, Counter
import bisect
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    S = input()
    dp = [0]*(N+1)
    dp[0] = S.count('.')
    for i in range(N):
        dp[i+1] = dp[i]-1 if S[i] == '.' else dp[i]+1
    print(min(dp))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = input()
    white = s.count(".")
    ans, black = white, 0
    for i in range(n):
        if s[i] == ".":
            white -= 1
        else:
            black += 1
        tmp = black + white
        if tmp < ans:
            ans = tmp
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
c=input()
w=c.count(".")
b=n-w
#全部黒にする場合
ans1=w
#全部白にする場合
ans2=b
"""
まずi=0とし、iを境に左にある黒の合計と右にある白の合計の最小を求める
"""
ans=ans1
tmp_b=0
tmp_w=w
for i in range(n):
    if c[i]==".":
        tmp_w-=1
    else:
        tmp_b+=1
    tmp_ans=tmp_b+tmp_w
    ans=min(ans,tmp_ans)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,input().replace('#','1').replace('.','0')))

cum=[0]
for i in range(N):
  cum.append(cum[-1]+S[i])
  
ans=10**20
for i in range(N+1):
  b = cum[i]
  w = N-i-(cum[-1]-cum[i])
  ans = min(ans,b+w)
  
print(ans)

Submission status: Accepted

Solution code:

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


white = 0
for i in s:
    if(i=='.'):
        white += 1
        
# 全部黒の場合
        
ans = white

# 左からi+1 個白の場合

now = white

for i in range(n):
    if(s[i]=='#'):
        now+=1
    else:
        now-=1
    ans = min(now,ans)

print(ans)

Submission status: Accepted

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

bcnt = S.count("#")
wcnt = N - bcnt

ans = wcnt
cntb = 0
cntw = 0
for i in range(N):
    if S[i] == "#":
        cntb += 1
    else:
        cntw += 1

    ans = min(ans, cntb + wcnt - cntw)


print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = "." + input() + "#"
B = [0]*(N+2)
W = [0]*(N+2)
b = 0
for k in range(N+2):
    if S[k] == "#":
        b += 1
    B[k] = b
w = 0
for k in range(N+1,-1,-1):
    if S[k] == ".":
        w += 1
    W[k] = w
ans = 10**10
for k in range(N+1):
    ans = min(ans,B[k]+W[k+1])
print(ans)

Submission status: Accepted

Solution code:
def solve(s):
    n = len(s)
    count_white_right = [0]*(n+1)
    count_black_left = [0]*(n+1)
    for i in range(n):
        count_black_left[i+1] = count_black_left[i] + (1 if s[i]=='#' else 0)
    for i in range(n)[::-1]:
        count_white_right[i] = count_white_right[i+1] + (1 if s[i]=='.' else 0)
    return min([count_black_left[i] + count_white_right[i] for i in range(n+1)])


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

if __name__ == "__main__":
    main()

import unittest
class Test(unittest.TestCase):
    def test1(self):
        self.assertEqual(solve('#.#'), 1)
    def test2(self):
        self.assertEqual(solve('#.##.'), 2)
    def test3(self):
        self.assertEqual(solve('.........'), 0)
    def test4(self):
        self.assertEqual(solve('#'), 0)
    def test5(self):
        self.assertEqual(solve('.'), 0)
    def test6(self):
        self.assertEqual(solve('#.'), 1)
    def test7(self):
        self.assertEqual(solve('##'), 0)
    def test8(self):
        self.assertEqual(solve('..'), 0)
    def test9(self):
        self.assertEqual(solve('.#'), 0)
    def test10(self):
        self.assertEqual(solve('#'*1000 + '.' * 999), 999)
    def test11(self):
        self.assertEqual(solve('#'*999 + '.' * 1000), 999)

Submission status: Accepted

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

ws = [0]
for c in S:
    ws.append(ws[-1] + int(c=='.'))

ans = N
for i,w in enumerate(ws):
    rw = ws[-1] - w
    lb = i - w
    ans = min(ans, rw+lb)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

A = [0]
a = 0
for s in S:
    if s == ".":
        a += 1
    A.append(a)

B = A[-1]

ans = N+1
for i, a in enumerate(A):
    score = (i - a) + B - a
    ans = min(ans, score)

print(ans)

Submission status: Accepted

Solution code:
_,s=open(b:=0);w=a=s.count('.')
for c in s:b+=(x:=c<'.');w-=(x<1);a=min(a,b+w)
print(a)

Submission status: Accepted

Solution code:
n=int(input());s=input();b=0;w=a=s.count('.')
for c in s:b+=(x:=c=='#');w-=(x<1);a=min(a,b+w)
print(a)

Submission status: Accepted

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

ans = float("inf")
b, w = 0, max_w
for s in S:
  if s == "#":
    b += 1
  else:
    w -= 1
  ans = min(ans, b+w)
print(min(ans, max_w, N-max_w))

Submission status: Accepted

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

white =[0]
black=[0]

for i in range(n):
    white.append(white[i]+int(s[i]=='.'))
    black.append(black[i]+int(s[i]=='#'))

ans = 300000
for i in range(n+1):
    if ans>black[i]+white[n]-white[i]:
        ans=black[i]+white[n]-white[i]

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def run():
    N = int(input())
    S = input()
    n_white = [0] * (N+1)
    black_position = []
    for i in range(N-1, -1, -1):
        n_white[i] = n_white[i+1]
        if S[i] == '#':
            black_position.append(i)
        else:
            n_white[i] += 1
    #print(black_position)
    #print(n_white)
    ans = min(len(black_position), N - len(black_position))
    for p, k in enumerate(black_position[::-1]):
        ans = min(ans, p + n_white[k])

    print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

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

if '.' not in S:
    print(0)
    exit()
elif '#' not in S:
    print(0)
    exit()

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

left_black = 0
right_white = white_sum
min_sum = white_sum
for i in range(N):
    if S[i] == '#':
        left_black += 1
    else:
        right_white -= 1

    min_sum = min(min_sum, left_black + right_white)
print(min_sum)

Submission status: Accepted

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

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

left_black = 0
right_white = white_sum
min_sum = white_sum
for i in range(N):
    if S[i] == '#':
        left_black += 1
    else:
        right_white -= 1

    min_sum = min(min_sum, left_black + right_white)
print(min_sum)

Submission status: Accepted

Solution code:
from itertools import *
n=int(input())
s=input()
w=[0]*(n+1)
b=[0]*(n+1)
for i,j in enumerate(s):
  if j=='.':w[i]=1
  else:b[i+1]=1
for i in range(n):
  w[n-i-1]+=w[n-i]
  b[i+1]+=b[i]
ans=10**18
for i,j in zip(w,b):
  ans=min(ans,i+j)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
v1 = [None]*n
v2 = [None]*n
v = 0
for i in range(n):
    if s[i]=="#":
        v += 1
    v1[i] = v
v1.insert(0,0)
v = 0
for i in range(n-1, -1, -1):
    if s[i]==".":
        v += 1
    v2[i] = v
v2.append(0)
ans = min((v1[i]+v2[i]) for i in range(n+1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
a = s.count('.')
g = [a]
b=0
while b<n:
  if s[b] == '.':
    a-=1
  else:
    a+=1
  g.append(a)
  b+=1
print(min(g))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
B=[]
W=[]
i=0
while i<N:
    if S[i]=='#':
        B.append(i)
    else:
        W.append(i)
    i+=1

X=len(B)
Y=len(W)
ans=0
i=j=0
while i<X and j<Y:
    if B[i]<W[j]:
        i+=1
        j+=1
        ans+=1
    else:
        j+=1
print(ans)

Submission status: Accepted

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

# In[6]:


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


# In[9]:


w = S.count(".")
b = 0
ans = min(w,N-w)
for i in range(N):
    if S[i] == ".":
        w -= 1
    else:
        b += 1
    ans = min(ans, w+b)
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
#laczil
def solve():
    N = int(input())
    S = input()
 
    left_black = 0
    right_white = 0
    for i in range(N):
        if S[i] == '.':
            right_white += 1
 
    ans = left_black + right_white
    for i in range(N):
        if S[i] == '#':
            left_black += 1
        else:
            right_white -= 1
        ans = min(ans, left_black + right_white)
    print(ans)
 
if __name__ == '__main__':
    solve()