Submission #69853787

---

Source Code Expand

// Problem: 'D - Pop and Insert'
// Contest: 'AtCoder - AtCoder Beginner Contest 426'
// URL: 'https://atcoder.jp/contests/abc426/tasks/abc426_d'
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by competitive-companion.el (https://github.com/luishgh/competitive-companion.el)

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

int n;
string s;

int res(char x) {
  int l = 0, r = n - 1;

  int ans = 0;
  int left = 0, right = 0;

  while (l <= r) {
    if (left == 0) {
      while (l < n and s[l] == x) {
        ans++;
        l++;
      }
      while (l < n and s[l] != x) left++, l++;
    }
    if (right == 0) {
      while (r >= 0 and s[r] == x) {
        ans++;
        r--;
      }
      while (r >= 0 and s[r] != x) right++, r--;
    }
    if (l > r) break;
    assert(s[l] == x and s[r] == x);
    if (left <= right) {
      ans += 2*left;
      left = 0;
    } else {
      ans += 2*right;
      right = 0;
    }
  }
  return ans;
}

void solve() {
  cin >> n;
  cin >> s;

  int ans = min(res('0'), res('1'));
  cout << ans << endl;
}

int main() {_;

  int ttt; cin >> ttt;
  while (ttt--) solve();

  return 0;
}

Submission Info

Judge Result