fork download
copy 
  1. //#include <bits/stdc++.h>
  2. #include<vector>
  3. #include <map>
  4. #include<deque>
  5. #include <iostream>
  6. #include<cmath>
  7. #include<algorithm>
  8. #define ll long long
  9. using namespace std;
  10.  
  11. int main() {
  12.     ios::sync_with_stdio(0);
  13.     cin.tie(NULL), cout.tie(NULL);
  14.     //freopen("mex.in", "r", stdin);
  15.  
  16.     ll t = 1; cin >> t;
  17.     while (t--) {
  18.         ll n,a=0,b=0;
  19.         cin >> n ;
  20.         string s;
  21.         cin >> s;
  22.         vector<ll>preA(n + 2), preB(n + 2),sufA(n+2),sufB(n+2);
  23.         for (ll i = 0; i < n; i++) {
  24.  
  25.             if (s[i] == 'a') {
  26.                 a++;
  27.                 preB[i + 1]+=b;
  28.             }
  29.             else {
  30.                 b++;
  31.                 preA[i + 1]+=a;
  32.             }
  33.             preB[i + 1] += preB[i];
  34.             preA[i + 1] += preA[i];
  35.         }
  36.  
  37.         a = 0, b = 0;
  38.         for (ll i = n-1; i >=0; i--) {
  39.  
  40.             if (s[i] == 'b') {
  41.                 b++;
  42.                 sufA[i + 1]+=a;
  43.             }
  44.             else {
  45.                 a++;
  46.                 sufB[i + 1]+=b;
  47.             }
  48.             sufB[i + 1] += sufB[i + 2];
  49.             sufA[i + 1] += sufA[i + 2];
  50.  
  51.         }
  52.  
  53.         ll mn = n;
  54.         for (ll i = 1; i <= n; i++) {
  55.             mn = min(preA[i] + sufA[i], mn);
  56.             mn = min(preB[i] + sufB[i], mn);
  57.         }
  58.         cout << mn << '\n';
  59.  
  60.     }
  61.     return 0;
  62. }
  63. /* 
  64.  
  65. */
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
4
abab
6
bababa
7
abababa
2
ab
1
b
stdout
copy 
1
2
2
0
0
https://ideone.com/yKD6XK
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!