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:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    n = ii()
    s = input()
    L = list(map(lambda x: 1 if x == '#' else 0, s))
    black_accum_count = [0] * (n + 1)    # black_accum_count[i] = s[:i].count('#')
    for i in range(n):
        black_accum_count[i+1] = black_accum_count[i] + L[i]
    
    # print(black_accum_count)
    cnt = inf
    for i in range(n+1):
        # s[:i] までは白、s[i:] からは黒になる場合の変更個数
        cnt = min(cnt, black_accum_count[i] + (n - i - (black_accum_count[n] - black_accum_count[i])))
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
left = [0] * N
if S[0] == '#':
    left[0] += 1
for i in range(1,N):
    left[i] = left[i-1]
    if S[i] == '#':
        left[i] += 1
if left[-1] == 0:
    print(0)
    exit()

right = [0] * N
if S[-1] == '.':
    right[-1] += 1
for i in reversed(range(N-1)):
    right[i] = right[i+1]
    if S[i] == '.':
        right[i] += 1
if right[0] == 0:
    print(0)
    exit()
ans = min(left[-1],right[0])
for i in range(N):
    if S[i] == '#':
        ans = min(ans,left[i]-1 + right[i])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

rw = S.count('.')
rb = S.count('#')
lw = 0
lb = 0

ans = min(rb, rw)
for s in S:
    if s == '.':
        lw += 1
        rw -= 1
    else:
        lb += 1
        rb -= 1
    ans = min(ans, lb+rw)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
a = 0
b = 0
A = []
for i in range(N):
  if S[i] == '.':
    a += 1
  else:
    b += 1
  A.append(b-a)
A.sort()
ans = min(a, b, a+A[0])
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
s = input()

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

Submission status: Accepted

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

b = 0
w = s.count(".")
ans = b + w
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())
S = input()
B = [0 for _ in range(N+1)]
W = [0 for _ in range(N+1)]
for i in range(N):
    B[i+1] = B[i] + (S[i] == '#')
for i in range(N, 0, -1):
    W[i-1] = W[i] + (S[i-1] == '.')
print(min(B[i]+W[i] for i in range(N+1)))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  divisors.sort()
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
S = S()
if S[0] == ".":
  L = [1]
else:
  L = [0]
for s in S[1:]:
  if s == ".":
    L.append(L[-1]+1)
  else:
    L.append(L[-1])

MIN = L[-1]
for i in range(N):
  MIN = min(MIN,(i+1)-L[i]+(N-i-1)-((N-i-1)-(L[-1]-L[i])))
print(MIN)

Submission status: Accepted

Solution code:
from itertools import accumulate


N = int(input())
S = input()
black = [0] * N
white = [0] * N
for i in range(N):
    if S[i] == "#":
        black[i] = 1
    else:
        white[i] = 1
black = list(accumulate(black, initial=0))
white = list(accumulate(white, initial=0))
ans = float("inf")
for i in range(N + 1):
    ans = min(ans, black[i] + white[N] - white[i])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right


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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    S = input()
    B = []
    W = []
    i = 0
    fin = None
    while i < N:
        if S[i] == '#':
            if i == N-1:
                B.append(1)
                fin = True
            else:
                tmp = 1
                while S[i+1] == '#':
                    tmp += 1
                    i += 1
                    if i == N-1:
                        fin = True
                        break
                B.append(tmp)
        else:
            if i == N-1:
                W.append(1)
                fin = False
            else:
                tmp = 1
                while S[i+1] == '.':
                    tmp += 1
                    i += 1
                    if i == N-1:
                        fin = False
                        break
                W.append(tmp)
        i += 1

    ans = sum(B)
    L = len(B)+len(W)
    B = B[::-1]
    W = W[::-1]
    now = ans
    if fin:
        for i in range(L):
            if i % 2 == 0:
                now -= B[i//2]
            else:
                now += W[i//2]
            ans = min(ans,now)
    else:
        for i in range(L):
            if i % 2 == 1:
                now -= B[i//2]
            else:
                now += W[i//2]
            ans = min(ans,now)
    print(ans)



    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

cnt = [0] * (n + 1)

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

ans = float("inf")

for i in range(0, n + 1):
    tmp = cnt[n] - cnt[i]  # cnt .. in right side
    tmp += i - cnt[i]  # cnt ## in left side
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
S = list(input())

tmp = S.count(".")
num = [0]*N
num_sharp = 0
num_peri = 0
for i in range(len(S)):
	if S[i] == "#":
		num_sharp += 1
	else:
		num_peri += 1
	num[i] = num_sharp + tmp-num_peri

print(min(tmp, min(num)))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
S = list(input())

tmp = S.count("#")
tmp2 = len(S) - tmp
num = [0]*N
num_sharp = 0
num_peri = 0
for i in range(len(S)):
	if S[i] == "#":
		num_sharp += 1
	else:
		num_peri += 1
	num[i] = num_sharp + tmp2-num_peri

print(min(tmp2, min(num)))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
S = input()

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

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


tmp_w = 0
for i in range(N-1, -1, -1):
	if S[i] == ".":
		tmp_w += 1
	w[i] = tmp_w

ans = min([b[i]+w[i] for i in range(N+1)])
#print(b)
#print(w)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
l=[[0,s.count('.')]]
for i in range(n):
    if s[i]=='.':
        l.append([l[-1][0],l[-1][1]-1])
    else:
        l.append([l[-1][0]+1,l[-1][1]])

ans=10**10
for i in range(n+1):
    ans=min(ans,sum(l[i]))

print(ans)

Submission status: Accepted

Solution code:
s=input()=='';b=[0]
for i in input():t=i=='.';b+=[b[-1]+1-t*2];s+=t
print(min([i+s for i in b]))

Submission status: Accepted

Solution code:
n=int(input());a=[0];b=[0];s=0
for i in input():t=i=='.';b+=[b[-1]+1-t*2];s+=t
print(min([i+s for i in b]))

Submission status: Accepted

Solution code:
n=int(input());a=[0];b=[0]
for i in input():t=i=='.';a+=[a[-1]+t];b+=[b[-1]+1-t*2];
print(min([i+a[n] for i in b]))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
cost = 0
bc = 0
for it in s:
    if it =="#":
        bc += 1
    else:
        if bc > 0:
            cost += 1
            bc -= 1
print(cost)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
S = list(sys.stdin.readline().rstrip())

count = []
cnt_b = 0
cnt_w = 0
for s in S:
    if s == "#":
        cnt_b += 1
    else:
        cnt_w += 1
    count.append((cnt_b, cnt_w))

ans_1 = N - cnt_b
ans_2 = N - cnt_w
ans_3 = float("inf")

for i, j in count:
    ans_3 = min(ans_3, i + cnt_w - j)

print(min(ans_1, ans_2, ans_3))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    input = stdin.readline

    n = int(input())
    s = input()
    a = [[0, 0] for _ in range(n)]
    if s[0] == '.':
        a[0][0] = 1
    else:
        a[0][1] = 1
    for i in range(1, n):
        if s[i] == '.':
            a[i][0] = a[i - 1][0] + 1
            a[i][1] = a[i - 1][1]
        else:
            a[i][0] = a[i - 1][0]
            a[i][1] = a[i - 1][1] + 1
    min = a[-1][0] if a[-1][0] < a[-1][1] else a[-1][1]
    for i in range(n):
        if min > a[-1][0] - a[i][0] + a[i][1]:
            min = a[-1][0] - a[i][0] + a[i][1]
    print(min)
main()

Submission status: Accepted

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

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

cnt = 0
for i in range(n-1, -1, -1):
    if s[i] == ".":
        cnt += 1
    countblack[i] = cnt

#print(countwhite)
#print(countblack)
res = 999999999999999
for i in range(n+1):
    res = min(res, countblack[i] + countwhite[i])
print(res)

Submission status: Accepted

Solution code:
import sys


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


sys.setrecursionlimit(20000000)

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


def main():
    N = int(input())
    S = list(input())
    numb = 0
    numw = S.count(".")
    answer = numb + numw
    for i in range(N):
        if S[i] == "#":
            numb += 1
        else:
            numw -= 1
        if answer > numb + numw:
            answer = numb + numw

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
n = int(input())
s = list(map(str, input().rstrip()))

ss = s.count("#")
sd = s.count(".")

if ss == 0 or sd == 0:
    print(0)
    sys.exit()

s = np.array([x == "#" for x in s])

dp = np.zeros([2, n], dtype=int)

# dp0は黒の数、dp0は白の数
dp[0] = s
dp[1] = ~s

dp = dp.cumsum(axis=1)

# 白の数は「それ以降の」と読み替える
dp[1] = dp[1].max() - dp[1]

print(min((dp[0] + dp[1]).min(), ss, sd))

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
s = input()
l = []
for i in s:
  if i==".":
    l.append(0)
  else:
    l.append(1)
l1 = list(accumulate([0]+l))
#print(l1)
l = []
for i in s[::-1]:
  if i==".":
    l.append(1)
  else:
    l.append(0)
l2 = list(accumulate([0]+l))[::-1]
#print(l2)
cou = 10**6
if "#" not in s or "." not in s :
  print(0)
else:
  #左が"."　右が"#"  左は#の個数調べて右は.の個数調べる
  for j,k in zip(l1,l2):
    a = j+k
    cou = min(cou,a)
  print(cou)

Submission status: Accepted

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

Submission status: Accepted

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

W=[1 if S[0]=="." else 0]
ans=float("inf")

for i in range(1,N):
  if S[i]==".":
    W.append(W[-1]+1)
  else:
    W.append(W[-1])
    
if W[-1]==0 or W[-1]==N:
  print(0)
  exit()

for i in range(N):
  cost_W = i+1-W[i]
  cost_B = W[-1]-W[i]
  cost=cost_W+cost_B
  #print(N, W[-1], i+1, W[i])
  #print(i,"cost_W:",cost_W,"cost_B:",cost_B,"Total",cost)
  ans=min(ans,cost)
ans=min(W[-1],N-W[-1],ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
from collections import defaultdict
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    S = input()[:-1]

    l = 0
    r = 0
    for i in range(N):
        if S[i] == ".":
            r += 1
    
    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:
def solve():
    N = int(input())
    S = input()
    white = [0] * (N+1)
    black = [0] * (N+1)
    for i in range(1,N+1):
        if S[i-1] == '.':
            white[i] = white[i-1] + 1
            black[i] = black[i-1]
        else:
            black[i] = black[i-1] + 1
            white[i] = white[i-1]
    
    ans = float('inf')
    for i in range(N+1):
        tmp = black[i] + white[-1] - white[i]
        ans = min(ans, tmp)
    
    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    S = input()
    white = [0] * (N+2)
    black = [0] * (N+2)
    for i in range(1,N+1):
        if S[i-1] == '.':
            white[i] = white[i-1] + 1
            black[i] = black[i-1]
        else:
            black[i] = black[i-1] + 1
            white[i] = white[i-1]
    
    ans = float('inf')
    for i in range(N+1):
        tmp = black[i] + white[-2] - white[i]
        ans = min(ans, tmp)
    
    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
S = input()
counter_s = Counter(S)
min_stone = counter_s.most_common()[-1][1]
if min_stone == N:
    min_stone = 0
A, B = 0, counter_s['.']
for s in S:
    if s == '#':
        A += 1
    else:
        B -= 1
    if min_stone > A+B:
        min_stone = A+B
print(min_stone)

Submission status: Accepted

Solution code:
import itertools

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

black = [0] * (N + 1)
white = [0] * (N + 1)
for i, s in enumerate(S, 1):
  if s == '#':
    black[i] += 1
  else:
    white[i] += 1

black = list(itertools.accumulate(black))
white = list(itertools.accumulate(white))

ans = N
num_W = white[-1]
for b, w in zip(black, white):
  ans = min(ans, b + (num_W-w))

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
s = readline().rstrip().decode('utf-8')
res = s.count(".")
ans = res
for i in range(n):
    if s[i] == "#":
        res += 1
    else:
        res -= 1
    ans = min(ans,res)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
leftid=-1
rightid=-1
blcnt=0
whcnt=0
cnt=0
ans=float("inf")
#.*#*になれば良い
#左と右から黒石・白石の数を数えていき、
#"a1,a2,a3,...,aN"列から構成しうるN+1この".#"境界
#について境界右で白い部分と左で黒い部分を変更する必要があるため、その和の最小が答え
leftblack=[0]*N
rightwhite=[0]*N
if S[0]=="#":
    leftblack[0]=1
if S[N-1]==".":
    rightwhite[N-1]=1
for i in range(1,N):
    if S[i]=="#":
        leftblack[i]=leftblack[i-1]+1
    else:
        leftblack[i] =leftblack[i - 1]
#print(leftblack)
for i in range(N-1,0,-1):
    if S[i-1]==".":
        rightwhite[i-1]=rightwhite[i]+1
    else:
        rightwhite[i-1] = rightwhite[i]
#print(rightwhite)
leftblack.insert(0,0)
rightwhite.insert(N,0)
#print(leftblack)
#print(rightwhite)
for i in range(N+1):# ####→.###→→....を考える
    ans=min(ans,leftblack[i]+rightwhite[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
A = [0]

for s in S:
    if s == '.':
        A.append(A[-1] + 1)
    else:
        A.append(A[-1])
ans = float('inf')
for i in range(N + 1):
    ansi = (i - A[i]) + (A[-1] - A[i])
    ans = min(ans, ansi)
print(ans)

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:
n = int(input())
s = input()
white = s.count(".")
black = s.count("#")

min_num = min(black, white)
black_num = 0
for i, color in enumerate(s, start = 1):
    if color == "#":
        black_num += 1
    min_num = min(min_num, black_num + white - (i - black_num))
    
print(min_num)