1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <algorithm>
#include <cstdio>
#include <cstring>

const int max_n = 500000;

int n;
char in[max_n];
char inSplit[max_n];
int na, nb;

int main() {
  scanf("%s", in);
  n = strlen(in);
  na = nb = 0;
  for (int i = 0; i < n; ++i) {
    if (in[i] == 'a') na++;
    else nb++;
  }
  if (na % 2 == 1 && nb % 2 == 1) {
    printf("-1\n");
    return 0;
  }
  long long cnt = 0;
  int a = 0, b = 0, move_to_right = 0;
  int pleft = 0, pright = (n + 1) / 2;
  for (int i = 0; i < n; ++i) {
    if (in[i] == 'a') {
      if (2 * a < na) {
        // stay left
        inSplit[pleft++] = 'a';
        cnt += move_to_right;
      } else {
        // move right
        inSplit[pright++] = 'a';
        ++move_to_right;
      }
      ++a;
    } else {
       if (2 * b < nb) {
        // stay left
        inSplit[pleft++] = 'b';
        cnt += move_to_right;
      } else {
        // move right
        inSplit[pright++] = 'b';
        ++move_to_right;
      }
      ++b;
    }
  }
  //printf("%s\n%lld\n", inSplit, cnt);
  int next_left = 0, next_right = n - 1;
  int search_left = 0, search_right = n - 1;
  while (next_left < next_right) {
    if (inSplit[next_left] == inSplit[next_right]) {
      next_left++;
      next_right--;
      continue;
    }
    if (search_left < next_left) search_left = next_left;
    if (search_right > next_right) search_right = next_right;
    while (inSplit[next_left] == inSplit[search_left]) ++search_left;
    while (inSplit[next_right] == inSplit[search_right]) --search_right;
    if (search_left - next_left < next_right - search_right) {
      cnt += search_left - next_left;
      std::swap(inSplit[search_left], inSplit[next_left]);
    } else {
      cnt += next_right - search_right;
      std::swap(inSplit[next_right], inSplit[search_right]);
    }
  }
  printf("%lld\n", cnt);
  return 0;
}