fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 2e5 + 5;
  5. const int OFFSET = 2e5 + 3;
  6.  
  7. int pref[MAXN];
  8. int last[2 * OFFSET];
  9. int last_time[2 * OFFSET];
  10. int test_case_num = 0;
  11.  
  12. void solve() {
  13.     test_case_num++;
  14.     int n;
  15.     string s;
  16.     cin >> n >> s;
  17.  
  18.     char plusChar = s[0];
  19.     int totalPlus = 0;
  20.     for (int i = 0; i < n; ++i) {
  21.         if (s[i] == plusChar) {
  22.             totalPlus++;
  23.         }
  24.     }
  25.     int totalMinus = n - totalPlus;
  26.     int diff = totalPlus - totalMinus;
  27.  
  28.     if (diff == 0) {
  29.         cout << 0 << '\n';
  30.         return;
  31.     }
  32.  
  33.     pref[0] = 0;
  34.     for (int i = 0; i < n; ++i) {
  35.         pref[i + 1] = pref[i] + (s[i] == plusChar ? 1 : -1);
  36.     }
  37.  
  38.     int ans = n + 1;
  39.  
  40.     for (int i = 0; i <= n; ++i) {
  41.         int want = pref[i] - diff;
  42.         int want_idx = want + OFFSET;
  43.  
  44.         if (last_time[want_idx] == test_case_num) {
  45.             ans = min(ans, i - last[want_idx]);
  46.         }
  47.  
  48.         int pref_idx = pref[i] + OFFSET;
  49.         last[pref_idx] = i;
  50.         last_time[pref_idx] = test_case_num;
  51.     }
  52.  
  53.     if (ans > n || ans == n) {
  54.         cout << -1 << '\n';
  55.     } else {
  56.         cout << ans << '\n';
  57.     }
  58. }
  59.  
  60. int main() {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(NULL);
  63.  
  64.     int t;
  65.     cin >> t;
  66.     while (t--) {
  67.         solve();
  68.     }
  69.  
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5572KB
comments (?)
stdin 
5
5
bbbab
6
bbaaba
4
aaaa
12
aabbaaabbaab
5
aabaa
stdout 
3
0
-1
2
-1
https://ideone.com/LUMXVl
language:
C++ (gcc 8.3)
created:
11 days 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!