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

numb=[0]
numw=[0]
cond="b"
for i in range(N):
    numb.append(numb[-1])
    numw.append(numw[-1])
    if S[i]=="#":
        numb[-1]+=1
    else:
        numw[-1]+=1

ans=[0 for _ in range(N+1)]
for j in range(N+1):
    ans[j]=numb[j]+(numw[-1]-numw[j])
print(min(ans))

Submission status: Accepted

Solution code:
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    s = input()
    a, b = [0], [0]
    for i in range(N):
        if s[i] == '#': a.append(a[-1]+1)
        else: a.append(a[-1])

        if s[-1-i] == '.': b.append(b[-1]+1)
        else: b.append(b[-1])
    b = b[::-1]
    output =  10 ** 6
    for x, y in zip(a, b): output = min(output, x + y)
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    #f len(set(S)) == 1:
    #    print(0)
     #   return

    baseblack = 0
    basewhite = sum([1 for x in S if x == '.'])
    ans = min(basewhite, N-basewhite)
    for i in range(N):
        baseblack += S[i] == '#'
        basewhite -= S[i] == '.'
        ans = min(ans, baseblack+basewhite)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
w = s.count('.')
b = 0
ans = w+b
for c in s:
    if c=='#':
        b += 1
    else:
        w -= 1
    ans = min(ans, w+b)
print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()

    white, black = 0, 1
    s = [int(i) for i in list(input().replace(".", "0").replace("#", "1"))]
    s.insert(0, 0)
    black_total = s.count(1)

    cnt = [0, 0]  # [white,black]
    ans = INF
    for i in range(n, -1, -1):
        ans = min(ans, black_total - cnt[black] + cnt[white])
        cnt[s[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnt = [s.count('.'), s.count('#')]

cnt0 = 0
cnt1 = 0
ans = float("inf")
for i in range(n):
    if s[i] == '.':
        cnt0 += 1
    if s[i] == '#':
        cnt1 += 1
    ans = min(ans, cnt1 + cnt[0] - cnt0)

if ans > min(cnt):
    print(min(cnt))
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    n = II()
    s = IS()
    cnt_b = 0
    cnt_w = s.count('.')
    cnt = cnt_w
    for si in s:
        if si == '#':
            cnt_b += 1
        else:
            cnt_w -= 1
        c = cnt_b+cnt_w
        if c < cnt:
            cnt = c
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    n = II()
    s = IS()
    cnt_b = 0
    cnt_w = s.count('.')
    cnt = cnt_w
    for i in range(n):
        if s[i] == '#':
            cnt_b += 1
        else:
            cnt_w -= 1
        cnt = min(cnt, cnt_b+cnt_w)
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    n = II()
    s = IS()
    cnt_b = 0
    cnt_w = s.count('.')
    cnt = cnt_w
    for si in s:
        if si == '#':
            cnt_b += 1
        else:
            cnt_w -= 1
        cnt = min(cnt, cnt_b+cnt_w)
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
s=list(ss())

mat=Counter(s)
black=mat["#"]
white=n-black

ans=white

if black==0 or white==0:
    print(0)
    exit()


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

    else:

        tmptoblack-=1
    
    ans=min(tmptowhite+tmptoblack,ans)

    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
S = str(input())

dp = [0]*(N+1)
temp = 0
for i in range(N):
    if S[i] == '.':
        temp += 1

dp[0] = temp

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

print(min(dp))

Submission status: Accepted

Solution code:
def tenka1bc19_c():
    N = int(input())
    S = str(input())

    # 白と黒の累積個数
    wt = [0]
    bk = [0]
    for s in S:
        w, b = wt[-1], bk[-1]
        if s == '.': w += 1
        else: b += 1
        wt.append(w)
        bk.append(b)

    # i番目までを白にして、i+1番目以降を黒にするときのコスト
    ans = 10**9
    for i in range(N+1):
        flip = bk[i] + wt[-1] - wt[i]
        ans = min(flip, ans)
    print(ans)

tenka1bc19_c()

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
w=s.count('.')
if s[0]=='.':
    sm=1
else:
    sm=0

def change(y):
    total=(y+1-sm)+(w-sm)
    return total
mn=change(0)
for i in range(1,n):
    if s[i]=='.':
        sm += 1
    mn=min(mn,change(i))
mn=min(mn,w)
print(mn)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
b_total = 0
w_total = 0
ans = 0
for i in range(n):
  if s[i] == '#':
    b_total += 1
  if s[i] == '.':
    w_total += 1
if b_total == n:
  print(0)
else:
  b_cnt = 0
  w_cnt = 0
  ans = b_cnt + (w_total - w_cnt)
  for i in range(n):
    if s[i] == '#':
      b_cnt += 1
    if s[i] == '.':
      w_cnt += 1
    cnt = b_cnt + (w_total - w_cnt)
    ans = min(ans, cnt)
  print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

n = int(input())
s = input()
siro = [0 for i in range(n+1)]
kuro = [0 for j in range(n+1)]
for i,c in enumerate(s):
    siro[i+1] = siro[i]
    kuro[i+1] = kuro[i]
    if c == '#':
        kuro[i+1]+=1
    else:
        siro[i+1]+=1
def getSiro(l,r):
    return siro[r]-siro[l]

def getKuro(l,r):
    return kuro[r]-kuro[l]

ans = inf
for i in range(n+1):
    ans = min(ans, getKuro(0,i)+getSiro(i,n))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ss = list(s)[::-1]

white = 0
black = 0
w = [0] * n
b = [0] * n

for i in range(n):
    if s[i] == '#':
        black += 1
    if ss[i] == '.':
        white += 1
    b[i] = black
    w[-i-1] = white

ans = 10**9

for i in range(n):
    if b[i] + w[i] < ans:
        ans = b[i] + w[i]

print(ans-1)

Submission status: Accepted

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

l = [0 for i in range(n)]
r = [0 for i in range(n)]
for i in range(1,n):
  rev = -(i+1)
  l[i] = l[i-1] + 1 if s[i-1] == "#" else l[i-1]
  r[rev] = r[rev+1] + 1 if s[rev+1] == "." else r[rev+1]

ans = 1e+9
for i in range(n):
  ans = min(ans, l[i] + r[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():

    N = int(input())
    S = list(input())
    bl = [0]*N
    wh = [0]*N

    from itertools import accumulate

    wh_num = 0
    for i in range(N):
        if S[i] == '#':
            bl[i] = 1
        else:
            wh[i] = 1

    bl = [0] + bl
    wh = [0]+wh

    # 累積和を格納したリスト．A[l:r]の総和はB[r] - B[l]
    bl = list(accumulate(bl))
    wh = list(accumulate(wh))

    # この問題は長さが1-Nの連続部分の和の最大値を出せというものなので以下の通り
    ans = N
    for i in range(N + 1):
        ans = min(ans, bl[i]+(wh[N]-wh[i]))
    print(ans)


resolve()

Submission status: Accepted

Solution code:
from itertools import*;input();s=input();print(min(map(sum,zip(*[list(accumulate([0]+list(map(int,s.translate(str.maketrans("#.","10"[::p]))))[::p]))[::p]for p in[1,-1]]))))

Submission status: Accepted

Solution code:
from itertools import*
n = int(input())
s = input()
b, w = [list(accumulate([0] + list(map(int, s.translate(str.maketrans("#.","10"[::p]))))[::p]))[::p] for p in [1,-1]]
m = float("inf")
for i in range(-~n):
    m = min(m, b[i] + w[i])
print(m)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()
    B = S.count("#")
    W = S.count(".")

    # 左からi文字目までの白の数
    n_white = []
    if S[0] == ".":
        n_white.append(1)
    else:
        n_white.append(0)
    for i in range(1, N):
        if S[i] == ".":
            n_white.append(n_white[-1] + 1)
        else:
            n_white.append(n_white[-1])

    # ....##### の並びにする.境目に関して全探索
    ans = min(B, W)
    for i in range(N):
        # 白に変える数
        cnt = i + 1 - n_white[i]

        # 黒に変える数
        cnt += n_white[-1] - n_white[i]

        if cnt < ans:
            ans = cnt

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

b_from_l = [0 for _ in range(N)]
w_from_r = [0 for _ in range(N)]

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

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

ans = min(S.count('.'), S.count('#'))
for i in range(N - 1):
    ans = min(ans, b_from_l[i] + w_from_r[i + 1])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
from collections import Counter, deque, defaultdict

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

mi = 10000000

c = Counter(S)
A = N - c["#"]
B = N - c["."]

l = 0
r = c["."]

for i in range(0, N):

    if S[i] == "#":
        l += 1
    else:
        r -= 1
    a = l + r
    if mi > a:
        mi = a

print(min(mi, A, B))

Submission status: Accepted

Solution code:
import collections

N = int(input().split()[0])
S = input()

index2count_dict = collections.defaultdict(int)
left_black_count = 0
for i, char in enumerate(S):
    index2count_dict[i] = left_black_count
    if char == "#":
        left_black_count += 1

right_white_count = 0
min_count = float("inf")
for i in range(N):
    index = N - (i + 1)
    count = index2count_dict[index] + right_white_count
    min_count = min(min_count, count)
    if S[index] == ".":
        right_white_count += 1

ans = min_count
print(ans)

Submission status: Accepted

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

cntW = 0
for s in S:
    if s == '.':
        cntW += 1

cntB = 0
MIN = 10 ** 5
for i in range(N+1):
    MIN = min(cntW+cntB,MIN)
    if i < N:
        if S[i] == '#':
            cntB += 1
        else:
            cntW -= 1

print(MIN)

Submission status: Accepted

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

ll=0 #左側の黒い数を保持
rr=s.count(".") #右側の白い数を保持

result=ll+rr
for item in s:
    if item=="#":
        ll+=1
    else:
        rr-=1
    
    result=min(result,ll+rr)

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
s = ns()

b, w = 0, 0
cub = [0] * (n + 1)
cuw = [0] * (n + 1)
for i in range(1, n + 1):
    cub[i] = cub[i - 1]
    cuw[i] = cuw[i - 1]
    cub[i] += s[i - 1] == '#'
    cuw[i] += s[i - 1] == '.'

ans = inf
for i in range(n + 1):
    ans = min(cub[i] + cuw[n] - cuw[i], ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().strip()

    c = collections.Counter(S)
    c2 = collections.Counter()
    ans = min(c['.'], c['#'])

    for i in range(N):
        c2[S[i]] += 1
        ans = min(ans, c2['#'] + c['.'] - c2['.'])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
countwhite=[0]*(n+1)
for i in range(n):
    if s[i]==".":
        countwhite[i+1]=countwhite[i]+1
    else:
        countwhite[i+1]=countwhite[i]
ans=10**8
for i in range(n+1):
    change=i-countwhite[i]+(countwhite[-1]-countwhite[i])
    ans=min(ans,change)
print(ans)

Submission status: Accepted

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

rightWhite = []
leftBlack = []

cntB = 0
cntW = 0

for i in range(N):
    rightWhite.append(cntW)
    leftBlack.append(cntB)
    if (S[i] == "#"):
        cntB += 1

    if (S[-i-1] == "."):
        cntW += 1

rightWhite = list(reversed(rightWhite))

ans = N

for i in range(N):
    ans = min(rightWhite[i] + leftBlack[i], ans)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
w=[0]*(n+1)
b=[0]*(n+1)
for i in range(1,n+1):
  w[i]=w[i-1]+1 if s[i-1]=="#" else w[i-1]
  b[-i-1]=b[-i]+1 if s[-i]=="." else b[-i]
print(min([x+y for x,y in zip(w,b)]))

Submission status: Accepted

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

B_sum = [0]*(N+1)
for i in range(N):
  if S[i] == "#":
    B_sum[i+1] = B_sum[i] + 1
  else:
    B_sum[i+1] = B_sum[i]

ans = float("INF")
for i in range(N+1):
  b_cnt = B_sum[i]
  w_cnt = N - i - (B_sum[N] - B_sum[i])
  tmp = b_cnt + w_cnt
  ans = min(ans, tmp)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    S=input()
    C=[[0,0] for _ in range(n)] #i以下の#の数，i以上の.の数
    cunt=0
    for i,s in enumerate(S):
        if s=='#':
            cunt+=1
        C[i][0]=cunt
    cunt=0
    for i in range(n-1,-1,-1):
        if S[i]=='.':
            cunt+=1
        C[i][1]=cunt  
    ans=C[0][1]
    for i in range(n-1):#.#をとる位置
        ans=min(ans,C[i][0]+C[i+1][1])
    ans=min(ans,C[n-1][0])
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()

    l_black = 0
    r_white = S.count(".")
    ans = r_white
    for i in range(N):
        if S[i] == "#":
            l_black += 1
        else:
            r_white -= 1
        count = l_black + r_white
        if count < ans:
            ans = count

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

sumBlack = [0]*(n+1)
sumWhite = [0]*(n+1)
for i in range(1,n+1):
    sumBlack[i] = sumBlack[i-1]
    if s[i-1] == '#':
        sumBlack[i] += 1

for i in range(n-1,-1,-1):
    sumWhite[i] = sumWhite[i+1]
    if s[i] == '.':
        sumWhite[i] += 1

ans = 12345678901234
for i in range(n+1):
    ans = min(ans,sumBlack[i]+sumWhite[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import sys
sys.setrecursionlimit(10**7)
def main():
  n=int(input())
  s=input()
  sw,sb=[0],[0]
  w,b=0,0
  for si in s:
    if si=='#':
      b+=1
    else:
      w+=1
    sw.append(w)
    sb.append(b)
  ans=n
  for i in range(n+1):
    ans=min(ans,sw[n]-sw[i]+sb[i])
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(str(input()))
WH = S.count(".")
ans = WH
for i in range(N):
  if S[i] == "#":
    WH += 1
  else:
    WH -= 1
  ans = min(ans, WH)

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    s = list(input())
    all_b = s.count("#")
    all_w = s.count(".")

    b = [0 for i in range(n)]
    w = [0 for i in range(n)]

    if s[0] == "#":
        b[0] = 1
    else:
        w[0] = 1
    for i in range(1, n):
        if s[i] == "#":
            b[i] = b[i - 1] + 1
            w[i] = w[i - 1]
        else:
            b[i] = b[i - 1]
            w[i] = w[i - 1] + 1

    ans = min(all_w, all_b)
    for i in range(n):
        ans = min(ans, b[i] + (all_w - w[i]))
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())

s=list(input())

black = [0]*n

white = [0]*n

for i in range(n):
    if s[i] == '.':
        white[i] = white[i-1]+1
        black[i] = black[i-1]
    else:
        white[i] = white[i-1]
        black[i] = black[i-1]+1
        
ans = 100000000

for i in range(n-1):
    if s[i] != s[i+1]:
        ans = min(ans,black[i]+(white[-1]-white[i+1]))
        
ans = min(ans,max(black),max(white))
print(ans)

Submission status: Accepted

Solution code:
# ed ans
n = int(input())
s = input()

if len(set(s)) == 1:
    print(0)
    exit()

# i について，whiteとblackの個数を見て最小

# 全部白，全部黒にする
# ans1 = s.count(".")
# ans2 = s.count("#")

# wwwbbbbbの形にする
# 初期
black_left = 0
white_right = s.count(".")
ans = white_right
# print(0, black_left, white_right, ans)

for ch in s:
    if ch == '#':
        black_left += 1
    else:
        white_right -= 1
    ans = min(ans, black_left + white_right)
    # print(i, black_left, white_right, ans)

# print(min(ans, ans2))
print(ans)

Submission status: Accepted

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

l = [[0, 0] for i in range(n + 1)]
for i in range(n):
    preB, preW = l[i]
    if s[i] == '#':
        l[i + 1] = [preB + 1, preW]
    else:
        l[i + 1] = [preB, preW + 1]

SUM_W = l[-1][1]
ans = 10 ** 10
for i, j in l:
    temp = i + SUM_W - j
    if temp < ans:ans = temp
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    S = input()
    
    w_acc, b_acc = [0], [0]
    for i in range(N):
        w_acc.append(w_acc[-1] + (S[i] == '.'))
        b_acc.append(b_acc[-1] + (S[i] == '#'))
    
    ans = w_acc[-1]
    for i in range(1, N + 1):
        ans = min(ans, b_acc[i] + w_acc[-1] - w_acc[i])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

right_white = S.count(".")
left_black = 0

ans = right_white + left_black
for i in range(N):
    if S[i] == ".":
        right_white -= 1
    else:
        left_black += 1
    ans = min(ans, right_white + left_black)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
S=[0 if i=='.' else 1 for i in input()]
if sum(S)==0 or sum(S)==n:
    print(0)
    exit()
sS=sum(S)
allblack=n-sum(S)
allwhite=sum(S)
bw=10**6
from itertools import accumulate
accS=list(accumulate(S))
for i in range(n):
    bw=min(bw,accS[i]+(n-(i+1))-(sS-accS[i]))
print(min(bw,allblack,allwhite))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    s = input()
    b = s.count('#')
    w = s.count('.')
    bb = 0
    ans = w
    for i in range(n):
        if s[i] == '#':
            bb += 1
        ww = n - (i + 1) - (b - bb)
        ans = min(ans, bb + ww)
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input() #sys.stdin.readlineは最後が改行


lan0 = []
lan1 = []

if s[0]=='#':
    lan0.append(0)

cnt0=0
cnt1=0

for i in range(n):
    if s[i] == '.':
        if cnt1 > 0:
            lan1.append(cnt1)
            cnt1=0
            cnt0=1
        else:
            cnt0+=1
    if s[i] == '#':
        if cnt0 > 0:
            lan0.append(cnt0)
            cnt0=0
            cnt1=1
        else:
            cnt1+=1

if cnt0>0:lan0.append(cnt0)
if cnt1>0:lan1.append(cnt1)



from itertools import accumulate
acc0 = list(reversed(lan0))
acc0 = list(accumulate(acc0))
acc0.reverse()
acc0 = acc0+[0] +[0]


acc1 = [0] + lan1
acc1 = list(accumulate(acc1))
acc1 = [0]+acc1

ans = n
for i in range(len(acc1)):
    ans = min(ans,acc0[i]+acc1[i])

print(ans)

Submission status: Accepted

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

bl = [0] * (N+1)    # 左に黒が何個あるか
wr = [0] * (N+1)    # 右に白が何個あるか
for i in range(N): bl[i+1] = bl[i] + (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)

ans = N+1
for i in range(N+1): ans = min(ans, bl[i]+wr[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    S = input()
    White = np.zeros(n + 1)
    Black = np.zeros(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 reversed(range(n)):
        if S[i] == ".":
            White[i] = White[i + 1] + 1
        else:
            White[i] = White[i + 1]

    res = White + Black
    print(int(min(res)))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    S = input()
    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 reversed(range(n)):
        if S[i] == ".":
            White[i] = White[i + 1] + 1
        else:
            White[i] = White[i + 1]

    res = f_inf
    for i in range(n + 1):
        res = min(res, White[i] + Black[i])

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

ans = n+1
for i in range(n+1):
  sub = 2*key[i]+n-i-key[-1]
  if ans > sub:
    ans = sub

print(ans)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    _ = int(input())
    S = input()

    if len(set(S)) == 1:
        return print(0)

    w = S.count('.')
    b = 0
    ans = w
    for s in S:
        if s == '#':
            b += 1
        else:
            w -= 1
        ans = min(ans, b + w)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
INF = 114514191981036436433-4
n = int(input())
s = input()

b = Counter(s)
ans = b["."]

cur = b["."]

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

Submission status: Accepted

Solution code:
n=int(input())
s=input()
ans=10**9
w=[0]*n
b=[0]*n
cw,cb=0,0
for i in range(n):
  if s[i]==".":
    cw+=1
  else:
    cb+=1
  w[i]=cw
  b[i]=cb

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

Submission status: Accepted

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

left_black = [0] * N
for i in range(N):
    if S[i] == '#':
        left_black[i] += 1
for i in range(N - 1):
    left_black[i+1] = left_black[i] + left_black[i+1]
left_black.insert(0, 0)
# print(left_black)

right_white = [0] * N
for i in range(N):
    if S[i] == '.':
        right_white[i] += 1
for i in range(N-1, 0, -1):
    right_white[i - 1] = right_white[i - 1] + right_white[i]
right_white.append(0)
# print(right_white)

m = 10 ** 6
for i in range(N):
    # if S[i] == '#':
    temp = left_black[i] + right_white[i + 1]
    # print(temp)
    m = min(m, temp)
print(m)

Submission status: Accepted

Solution code:
N,S = open(0).read().split()
ans = 0
ls = []
cnt = 1
p = S[0]
for c in S[1:]:
  if p!=c:
    p = c
    ls.append(cnt)
    cnt = 1
  else:
    cnt += 1
ls.append(cnt)
b = 0
w = 0
if S[0]=='.':
  w = sum(ls[i] for i in range(0, len(ls),2))
  ans = b+w
  for i in range(len(ls)):
    if i%2==0:
      w -= ls[i]
    else:
      b += ls[i]
    ans = min(ans,w+b)
else:
  w = sum(ls[i] for i in range(1,len(ls),2))
  ans = b+w
  for i in range(len(ls)):
    if i%2==0:
      b += ls[i]
    else:
      w -= ls[i]
    ans = min(ans,w+b)

print(ans)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    # ans_w, ans_b = 0, 0

    # started = False
    # for s in S:
    #     if s == '#':
    #         started = True
    #     if started and s == '.':
    #         ans_w += 1
    # started = False
    # for i in range(N):
    #     s = S[N - 1 - i]
    #     if s == '.':
    #         started = True
    #     if started and s == '#':
    #         ans_b += 1
    # print(min(ans_w, ans_b))
    Ws, Bs = [], []
    c = S[0]
    l = 1
    for i in range(1, N):
        s = S[i]
        if c == s:
            l += 1
        else:
            if c == '.':
                Ws.append(l)
            else:
                Bs.append(l)
            l = 1
            c = s
    if c == '.':
        Ws.append(l)
    else:
        Bs.append(l)
    # print(Ws, Bs)
    len_ws = len(Ws)
    len_bs = len(Bs)
    if len_ws == 0 or len_bs == 0:
        print(0)
        return
    if len_ws == 1:
        if len_bs == 1:
            if S[0] == '.':
                print(0)
            else:
                print(min(Bs[0], Ws[0]))
        else:
            # len_bs == 2
            print(min(Ws[0], Bs[0]))
        return
    if len_bs == 1:
        # len_ws == 2
        print(min(Ws[1], Bs[1]))
        return

    # len_ws >= 2 and len_bs >= 2
    sum_w_s, sum_w_r, sum_b_s, sum_b_r = [0]*len_ws, [0]*len_ws,  [0]*len_bs, [0]*len_bs
    sum_w_s[0] = Ws[0]
    sum_w_r[0] = Ws[-1]
    sum_b_s[0] = Bs[0]
    sum_b_r[0] = Bs[-1]
    for i in range(1, len_ws):
        sum_w_s[i] = sum_w_s[i - 1] + Ws[i]
        sum_w_r[i] = sum_w_r[i - 1] + Ws[len_ws - 1 - i]
    for i in range(1, len_bs):
        sum_b_s[i] = sum_b_s[i - 1] + Bs[i]
        sum_b_r[i] = sum_b_r[i - 1] + Bs[len_bs - 1 - i]
    # print(sum_w_s, sum_w_r, sum_b_s, sum_b_r)
    ans = min(sum_w_s[-1], sum_b_s[-1])
    if S[0] == '#':
        for i in range(len_ws - 1):
            a = sum_b_s[i] + sum_w_r[len_ws - 2 - i]
            ans = min(a, ans)
    else:
        ans = min(ans, sum_w_s[-1] - Ws[0])
        for i in range(len_ws - 1):
            a = sum_w_r[i] + sum_b_s[len_bs - 2 - i]
            ans = min(a, ans)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

wr = [0] * (N+1)
bl = [0] * (N+1)

def solve():
    bc = 0
    for i in range(N):
        bl[i] = bc
        if S[i] == '#':
            bc += 1
    bl[N] = bc
    wc = 0
    for i in range(N-1, -1, -1):
        if S[i] == '.':
            wc += 1
        wr[i] = wc
    wr[N] = 0
    minval = N + 100
    mini = None
    for i in range(N+1):
        cost = bl[i] + wr[i]
        if minval > cost:
            minval = cost
            mini = i
    return minval

print(solve())