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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right


def solve():
    N = II()
    S = LS()

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,S = open(0).read().split()
N = int(N)
w = S.count('.')
ans = float('inf')
ws = [0] * (N+1)
for i in range(1,N+1):
    ws[i] = ws[i-1]
    if S[i-1] == '.':
        ws[i] += 1
for i in range(N+1):
    ans = min(ans,i-2*ws[i]+w)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

acc_w = [0] * (N + 1)
acc_b = [0] * (N + 1)
for i in range(1, N + 1):
    c = S[i - 1]
    acc_w[i] = acc_w[i - 1] + (1 if c == '.' else 0)
    acc_b[i] = acc_b[i - 1] + (1 if c == '#' else 0)

ans = INF
for i in range(N + 1):
    now = acc_b[i] + acc_w[-1] - acc_w[i]
    ans = min(ans, now)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
s = input()
w = s.count(".")
b = 0
ans = w
for i in s:
    b += i =="#"
    w -= i == "."
    ans = min(ans, w+b)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
white = 0
black = 0
for i in range(n):
    if s[i] == '.':
        white+=1

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

Submission status: Accepted

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

l_blacks = 0
r_whites = 0

for c in S:
    if c == '.':
        r_whites += 1

mins = r_whites
for c in S:
    if c == '.':
        r_whites -= 1
    if c == '#':
        l_blacks += 1
    mins = min(mins, r_whites + l_blacks)
print(mins)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    # ゴールのイメージ：.........###########
    # 左から何個分まで白にするかで場合分けして最小回数を探索
    black_cum_sum = [0] * N
    for i, c in enumerate(S):
        if S[i] == '#':
            black_cum_sum[i] += 1
        if i > 0:
            black_cum_sum[i] += black_cum_sum[i - 1]
    ans = N - black_cum_sum[N - 1]  # 全部黒にするケース
    for n in range(1, N + 1):
        # 白をn個連続にするケース
        # 前半は黒を白に
        c = black_cum_sum[n - 1]
        # 後半は白を黒に
        c += (N - black_cum_sum[N - 1]) - (n - black_cum_sum[n - 1])
        ans = min(ans, c)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    n_w_all = S.count(".")
    n_b_all = S.count("#")
    n_w = 0
    n_b = 0
    ans = min(n_w_all, n_b_all)
    for i in range(N - 1):
        if S[i] == ".":
            n_w += 1
        else:
            n_b += 1
        num = n_b + (n_w_all - n_w)
        if num < ans:
            ans = num

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

d=[0]*n
d2=[0]*n
d[0]=1 if s[0]=="#" else 0
d2[-1]=1 if s[-1]=="." else 0

for i in range(1,n):
  d[i]=d[i-1]+1 if s[i]=="#" else d[i-1]
  d2[-1-i]=d2[-i]+1 if s[-i-1]=="." else d2[-i]

m=n
for i in range(n):
  m=min(m,d[i]+d2[i])
print(m-1)

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(lambda x:1*(x=="#"),input()))

L=M=S.count(0)

for i in range(N):
    if S[i]:
        M+=1
    else:
        M-=1
        L=min(L,M)
print(L)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
black = 0
ans = 0

for s in S:
    if s == "#":
        black += 1
    else:
        if black > 0:
            ans += 1
            black -= 1

print(ans)

Submission status: Accepted

Solution code:
N,S = open(0).read().split()
N=int(N)
S=[s == "." for s in list(S)]

w = sum([1 if s else 0 for s in S])
b = 0
m = w + b
for s in S:
    if s:
        w -= 1
    else:
        b += 1
    m = min(m, w + b)
print(m)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline

sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    n = int(input())
    s = input()
    w = s.count(".")
    b = n - w
    ans = min(w, b)
    b = 0
    for i in range(n):
        if s[i] == ".":
            w -= 1
        else:
            b += 1
        ans = min(ans, w + b)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

wlist = [0] * (n + 1)
blist = [0] * (n + 1)

for i in range(n):
    if s[i] == ".":
        wlist[i + 1] = wlist[i] + 1
        blist[i + 1] = blist[i]
    elif s[i] == "#":
        wlist[i + 1] = wlist[i]
        blist[i + 1] = blist[i] + 1

ans = n

for i in range(n + 1):
    tmp = blist[i] + (wlist[n] - wlist[i])
    if ans > tmp: ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    S = input()
    ans = S.count('.')
    score = ans
    for c in S:
        if c == '.':
            score -= 1
        else:
            score += 1
        ans = min(ans, score)
    print(ans)
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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


def resolve():
    n = int(input())
    s = input()

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

    b = [0] + list(accumulate(b))
    w = [0] + list(accumulate(w))
    res = f_inf
    for i in range(n + 1):
        c_b = w[-1] - w[i]
        c_w = b[i]
        res = min(res, c_b + c_w)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

black=s.count("#")
white=s.count(".")
b=0
w=0
ans=float('inf')

for i in range(n):
  if s[i]=="#":
    b+=1
  elif s[i]==".":
    w+=1
  
  right_change=white-w
  now=b+right_change
  # print(now)
  ans=min(ans,now)
  
print(min(ans,black,white))

Submission status: Accepted

Solution code:
import sys

n=int(input())
c=input()
black=c.count("#")
white=c.count(".")

if black==n:
  print(0)
  sys.exit()

b=0
w=0
now=0
ans=float('inf')

for i in range(n):
  if c[i]=="#":
    b+=1
  w=(i+1)-b

  now=b+(white-w)
  ans=min(ans,now)
  
print(min(ans,white))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    s = input()
    ans = s.count(".")
    cur = ans

    for i, char in enumerate(s):
        if char == ".":
            cur -= 1
        else:
            cur += 1
        ans = min(ans, cur)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys

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

    n = int(input())
    s = input()
    cnt = [0]
    for i in range(n):
        cnt.append(cnt[-1])
        if s[i] == '#':
            cnt[-1] += 1
    
    m = cnt[-1]
    ans = 10**9
    for i in range(n+1):
        tmp = cnt[i] + (n-i)-(m-cnt[i])
        ans = min(tmp, ans)
    print(ans)


        
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [0, 0]
for c in input():
    if c == '.':
        dp[1] += 1
    else:
        dp[1] = min(dp[1], dp[0])
        dp[0] += 1
print(min(dp))

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N = int(input())
s = input().rstrip()
cntb =0
cntw = s.count('.')
ans =cntw
for i in range(len(s)):
    if s[i] == '#':
        cntb +=1
    else:
        cntw -=1
    ans = min(ans,cntb+cntw)
print(ans)

Submission status: Accepted

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

b_cnt = [0] * (n + 1)
for i in range(n):
    if s[i] == '#':
        b_cnt[i + 1] = b_cnt[i] + 1
    else:
        b_cnt[i + 1] = b_cnt[i]

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

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter
N = int(input())
S = list(input())
kuro = [0]*N
shiro = [0]*N
ans = N

for i in range(N):
    if S[i] == "#":
        kuro[i] = 1
    else:
        shiro[i] = 1
shiro.reverse()
shiro = list(accumulate(shiro))
kuro = list(accumulate(kuro))

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

ans = min(ans, kuro[N-1])
S = Counter(S)
ans = min(ans, S["#"], S["."])
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

lis = [1 if s=='#' else 0 for s in S]
from itertools import accumulate
lis = list(accumulate(lis))

ans = 10**18
cnt = 0
for i in range(N-1, -1, -1):
    s = S[i]
    ans = min(ans, cnt+lis[i])
    if s=='.':
        cnt += 1
ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    S = input()
    l, r = 0, S.count('.')
    ans = l + r
    for i in range(n):
        if S[i] == '#': l += 1
        else: r -= 1
        ans = min(ans, l + r)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

num_black = 0
num_white = 0
# 該当部分を含まずに、「より左」にある黒の数
left_black = [0] * (n+1)
# 該当部分を含まずに、「より左」にある白の数
left_white = [0] * (n+1)
for i in range(n):
    if s[i] == '#':
        num_black += 1
    else:
        num_white += 1
    left_black[i+1] = num_black
    left_white[i+1] = num_white
# 該当部分を含んで、「より右」にある白の数
right_white = [0] * (n+1)
for i in range(n,-1,-1):
    right_white[i] = num_white - left_white[i]

# インデックスiから右（iを含む）は全て黒にする、として数える
ans = num_white
for i in range(n+1):
    num_to_change = left_black[i] + right_white[i]
    ans = min(ans, num_to_change)
print(ans)

Submission status: Accepted

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

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

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

print(min(ans))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
wh = [0] * n
bl = [0] * n

w , b = 0,0
for i in range(n):
  if s[i] == '.':
    w += 1
  else:
    b += 1
  wh[i] = w
  bl[i] = b
ans = n
wtot = wh[-1]
btot = bl[-1]
for i in range(n):
  x = (wtot - wh[i]) + bl[i]
  # print (bl[i], (wtot - wh[i]))
  ans = min(ans, x)
ans = min(ans, wtot)
print (ans)

Submission status: Accepted

Solution code:

import bisect

N = int(input())
S = '0'+input()+'0'

lst1 = []
lst2 = [0]*(N+2)


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

if len(lst1) == N or lst2[1] == N:
  print(0)
  exit()
  
rlt = N+1
for i in range(len(lst1)):
  rlt =  min(rlt, i+lst2[lst1[i]])
  
rlt = min(len(lst1), rlt)
  
print(rlt)

Submission status: Accepted

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

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

b = 0
w = 0
stones = [(0,0)]
for i in S:
    if i == "#":
        b += 1
    else:
        w += 1
    stones.append((b,w))

bb = S.count("#")
ww = S.count(".")

ans = 1e9

for b,w in stones:
    ans = min(ans,b+ww-w)

print(ans)

Submission status: Accepted

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


def main():
    n = int(input().strip())
    S = input().strip()
    query_table = [0] * (n+1)
    for i, s in enumerate(S):
        if s == "#":
            query_table[i + 1] = query_table[i] + 1
        else:
            query_table[i + 1] = query_table[i]
    ans = float("inf")

    for ptr in range(n+1):
        # left side
        left_black = query_table[ptr]
        left_white = ptr - left_black

        # right side
        right_black = query_table[n] - left_black
        right_white = n - ptr - right_black
        ans = min(ans, left_black+right_white)

    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
ans = 0
c = 0
for i in range(n):
    if s[i] == "#":
        c += 1
    else:
        if c >= 1:
            ans += 1
            c -= 1
    
print(ans)

Submission status: Accepted

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

ans = 10**9

T = "#."
W = '.'
B = '#'

dp_blk = [0]*(N+1)
dp_wht = [0]*(N+1)

if all([B==c for c in S]) or all([W==c for c in S]):
    print(0)
    exit(0)

for ix in range(N):
    if S[ix] == B:
        dp_blk[ix+1] += dp_blk[ix] + 1
        dp_wht[ix+1] += dp_wht[ix]
    else:
        dp_wht[ix+1] += dp_wht[ix] + 1
        dp_blk[ix+1] = dp_blk[ix]

# print("dp_blk", dp_blk)
# print("dp_wht", dp_wht)

for lix in range(N+1):
    b_flip = dp_blk[lix]
    w_flip = dp_wht[N] - dp_wht[lix]
    flip = b_flip + w_flip
    # print(lix, flip)
    if ans > flip:
        ans = flip

# ab = N - dp_blk[N]
# aw = N - dp_wht[N]
# ans = min(ab, aw, ans)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
s=input()
mae=[0]*(n+2)
usiro=[0]*(n+2)
for i in range(1,n+1):
    if s[i-1]=="#":
        mae[i]+=1
    mae[i]+=mae[i-1]
    if s[n-i]==".":
        usiro[n-i+1]+=1
    usiro[n-i+1]+=usiro[n-i+2]

ans=2*n
for i in range(1,n+2):
    ans=min(ans,mae[i-1]+usiro[i])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
解説PDFを読んだ。
"""

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

    hash_counter = 0
    dot_counter = S.count(".")
    answer = dot_counter
    for i in range(N):
        if S[i] == "#":
            hash_counter += 1
        else:
            dot_counter -= 1
        answer = min(answer, hash_counter+dot_counter)
    print(answer)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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


def resolve():
    n = int(input())
    s = input()

    black, white = [0] * n, [0] * n
    for i in range(n):
        if s[i] == "#":
            black[i] = 1
        else:
            white[i] = 1

    acc_b = [0] + list(accumulate(black))
    acc_w = [0] + list(accumulate(white))

    res = f_inf
    for left in range(n + 1):
        change_w = acc_b[left]
        change_b = acc_w[n] - acc_w[left]
        res = min(res, change_w + change_b)
    print(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()

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

    w = [0] * n
    cnt = 0
    for i in reversed(range(n)):
        if s[i] == ".":
            cnt += 1
        w[i] = cnt

    res = f_inf
    w = w + [0]
    b = [0] + b
    for i, j in zip(w, b):
        res = min(res, i + j)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
b=[0 for i in range(n)]
tmp=0
for i in range(n-1,-1,-1):
    if s[i]=="#":
        tmp+=1
    b[i]=tmp
w=[0 for i in range(n)]
tmp=0
for i in range(n):
    if s[i]==".":
        tmp+=1
    w[i]=tmp
tmp=0
ans=float("inf")
for i in range(n):
    tmp=n-(w[i]+b[i])
    if tmp<ans:
        ans=tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

lb = [0] * (N+1)
for i, c in enumerate(S, 1):
    lb[i] = lb[i-1] + (1 if c=='#' else 0)

ans = N + 100
bl = lb[-1]
for i in range(N+1):
    j = i+1
    left = lb[i]
    right = N - i - (bl - lb[i])
    ans = min(ans, left+right)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
n = S.count('.')
ans = min(n, N-n)
lsc = 0
rsc = N-n
for i, c in enumerate(S):
    if c == '#':
        lsc += 1
        rsc -= 1
    a = lsc + ((N-i-1) - rsc)
    ans = min(ans, a)

print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,comb,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
s = input()
a = [0]*(n+1)
b = [0]*(n+1)
# a[i]: s[:i-1]を白とするための変更個数
# b[i]: s[i:]を黒とするための変更個数

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

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

c = [0]*(n+1)
for i in range(n+1):
    c[i] = a[i] + b[i]

print(min(c))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    W = [0] * (N+1)  # W[j]-W[i]: 区間[i, j)の白の数
    B = [0] * (N+1)  # B[j]-B[i]: 区間[i, j)の黒の数
    for i in range(N):
        s = S[i]
        W[i+1] = W[i] + 1 if s == "." else W[i]
        B[i+1] = B[i] + 1 if s == "#" else B[i]
    # i以上を黒に、i未満を白にする
    # .....##### になればOK
    ans = N
    for i in range(N+1):
        b2w = W[N] - W[i]
        w2b = B[i] - B[0]
        ans = min(ans, b2w + w2b)
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
n = int(input())
stones = input()
white = stones.count('.')
black = 0
ans = white
for c in stones:
    if c == '#':
        black += 1
    else:
        white -= 1
    score = black + white
    ans = min(score, ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
S = list(input())
ans = 10 ** 9
hash = [0] * (N + 1)
memo = 0
for i in range(N):
  if S[i] == "#":
    memo += 1
  hash[i + 1] = memo
dot = [0] * (N + 1)
memo = 0
for i in range(N - 1,-1,-1):
  if S[i] == ".":
    memo += 1
  dot[i] = memo    
for i in range(N + 1):
  ans = min(ans, hash[i] + dot[i])
print(ans)

Submission status: Accepted

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

res = 1 << 40
num_black = 0
num_white = s.count('.')
for i in range(n):
    res = min(res, num_black + num_white)
    if s[i] == '.':
        num_white -= 1
    else:
        num_black += 1
        
res = min(res, num_black + num_white)
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

a = [0] * (n + 1)
b = [0] * (n + 1)

for i in range(n):
    #先頭からi番目までの#の数
    if s[i] == '#':
        a[i + 1] = 1
    #末尾からi番目までの.の数
    if s[n - i - 1] == '.':
        b[n - i - 1] = 1
    #累積和をとる
    a[i + 1] += a[i]
    b[n - i - 1] += b[n - i]

ans = 100100100

for i in range(n):
    #i番目を境に分けた時に入れ替える数の最小値
    ans = min(ans, a[i] + b[i + 1])

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=[0]
for i in s:
    if i==".":a+=[a[-1]+1]
    else:a+=[a[-1]]
w=s.count(".")
print(min(i-a[i]*2+w for i in range(n+1)))

Submission status: Accepted

Solution code:
n=int(input())
s=input()
a=[0]
for i in s:
    if i==".":a+=[a[-1]+1]
    else:a+=[a[-1]]
w=s.count(".")
print(min(i-a[i]+w-a[i] for i in range(n+1)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

from itertools import groupby

gr=groupby(s)
#flg=0:白の状態
flg=0
black=[]
white=[]
for k,v in gr:
    if flg==0 and k=='#':
        flg=1
        black.append(len(list(v)))
    elif flg==1:
        if k=='#':
            black.append(len(list(v)))
        else:
            white.append(len(list(v)))
if len(black)==0 or len(white)==0:
    print(0)
    exit(0)




cnt=sum(white)
ans=[cnt]
for i in range(len(white)):
    cnt+=(black[i]-white[i])
    ans.append(cnt)

print(min(ans))

Submission status: Accepted

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

tmp = 10 ** 9
cntB = S.count("#")
cnt = 0
for i, s in enumerate(S):
    if s == "#":
        tmp = min(tmp, cnt + N - i - (cntB - cnt))
        cnt += 1

print(min(cntB, tmp))

Submission status: Accepted

Solution code:
N=int(input())
S=input()
W=[0]*N
B=[0]*N
tmp=0
for i in range(N):
	if S[i]=="#":
		tmp+=1
	B[i]=tmp
tmp=0
for i in range(N):
	if S[i]==".":
		tmp+=1
	W[i]=tmp
Max_W=(max(W))
tmp=float("inf")
for i in range(N-1):
	tmp=min(tmp,B[i]+(Max_W-W[i]))
print(min(tmp,max(B),max(W)))

Submission status: Accepted

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

ans, lb, rw = s.count('.'), 0, s.count('.')
for i in s:
    if i == '#':
        lb += 1
    elif i == '.':
        rw -= 1
    ans = min(ans, lb + rw)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
ans = 10**6
w = [0]
for i in range(n):
    w.append(w[i] + (s[i] == "."))

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

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    S = list(in_s())[::-1]

    cb = [0] * (N + 1)
    cw = [0] * (N + 1)
    for i in range(N):
        if S[i] == '#':
            cb[i + 1] = 1
        else:
            cw[i + 1] = 1

    for i in range(N):
        cb[i + 1] += cb[i]
        cw[i + 1] += cw[i]

    ans = S.count('.')
    for i in range(N + 1):
        ans = min(ans, cw[i] + cb[N] - cb[i])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
accum=[0]*n
if s[0]=="#":
    accum[0]=1
for i in range(n-1):
    accum[i+1]+=accum[i]+(s[i+1]=="#")
accum=[0]+accum
ans=10**18
for i in range(n+1):
    ans=min(ans,accum[i]+n-i-accum[n]+accum[i])
#print(accum)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    white = S.count('.')
    black = 0
    ans = white + black
    for i in S:
        if i == '.':
            white -= 1
        else:
            black += 1
        ans = min(white + black, ans)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    S=input()
    bk=S.count("#")
    ans=N-bk
    w=0
    for i in range(N):#i番目まで白，i+1以降黒
        if S[i]=="#":
            bk-=1
        else:
            w+=1
        temp=(i+1-w)+(N-i-1-bk)
        ans=min(ans,temp)
    print(ans)
        

main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
S = list(input())
white = [0] * (n+1)
black = [0] * (n+1)
for i in range(n):
    white[i+1] = white[i]  + (1 if S[i] == '.' else 0)
    black[i+1] = black[i] + (1 if S[i] == '#' else 0)
res = float('inf')
# 累積和で最小値を求める
for left in range(n+1):
    tmp = 0
    # leftを全部白に、
    tmp += black[left] - black[0]
    tmp += white[n] - white[left]
    res = min(res,tmp)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
S = input()
#右にある白，左にある黒
cnt = [0]*(n+1)
white = S.count(".")
black = 0
cnt[0] = white
for i in range(n):
    if S[i] == ".":
        white -= 1
    else:
        black += 1
    cnt[i+1] = black + white
print(min(cnt))