Submission #69854677

---

Source Code Expand

from itertools import accumulate

for _ in range(int(input())):
  n = int(input())
  S = list(map(int, input()))
  T0_ = [1 if S[i]==0 else 0 for i in range(n)]
  T1_ = [1 if S[i]==1 else 0 for i in range(n)]
  T0 = list(accumulate(T0_))
  T1 = list(accumulate(T1_))
  
  l = 0
  ans = n**2
  while l<n:
    r = l+1
    while r<n and S[l]==S[r]:
      r += 1

    t0 = (T0[l-1] if l-1>=0 else 0)+T0[n-1]-T0[r-1]
    t1 = (T1[l-1] if l-1>=0 else 0)+T1[n-1]-T1[r-1]
    if S[l]==0:
      ans = min(ans, t0*2+t1)
    else:
      ans = min(ans, t1*2+t0)
    l = r
  print(ans)

Submission Info

Judge Result