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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <algorithm>
#include <deque>
#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  string s;
  cin >> s;
  // for (int i = 0; i < 100000; i++) {
  //   s += "a";
  // }
  // for (int i = 0; i < 100000; i++) {
  //   s += "b";
  // }

  // for (int i = 0; i < 267; i++) {
  //   s += "babbabaa";
  // }
  // s += "aab";
  // for (int i = 0; i < 267; i++) {
  //   s += "babbabaa";
  // }
  int n = s.size();
  // for (int i = 0; i < n; i++) {
  //   if (s[i] == 'a') {
  //     s[i] = 'b';
  //   } else {
  //     s[i] = 'a';
  //   }
  // }
  // cout << s << "\n";
  // deque<int> a_idx;
  // deque<int> b_idx;
  set<int> a_idx;
  set<int> b_idx;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'a') {
      // a_idx.push_back(i);
      a_idx.insert(i);
    } else {
      // b_idx.push_back(i);
      b_idx.insert(i);
    }
  }
  int a_count = a_idx.size();
  int b_count = b_idx.size();
  if (n % 2 == 0 && a_count % 2 + b_count % 2 != 0) {
    cout << -1 << "\n";
    return 0;
  }
  ll ret = 0;
  for (int i = 0; i < n / 2; i++) {
    // cout << s << "\n";
    // for (auto it = a_idx.begin(); it != a_idx.end(); it++) {
    //   cout << *it << ' ';
    // }
    // cout << "\n";
    // for (auto it = b_idx.begin(); it != b_idx.end(); it++) {
    //   cout << *it << ' ';
    // }
    // cout << "\n";
    int j = n - i - 1;
    if (i == j) {
      break;
    }
    if (s[i] != s[j]) {
      if (s[i] == 'a') {
        if (abs(i - *b_idx.begin()) < abs(j - *a_idx.rbegin())) {
          int idx = *b_idx.begin();
          s[idx] = 'a';
          s[i] = 'b';
          // a_idx.pop_front();
          // a_idx.push_front(idx);
          // b_idx.pop_front();
          a_idx.erase(a_idx.begin());
          a_idx.insert(idx);
          b_idx.erase(b_idx.begin());
          b_idx.erase(--b_idx.end());
          ret += abs(i - idx);
          // cout << "switch 1: " << idx << " " << j << "\n";
        } else {
          int idx = *a_idx.rbegin();
          s[idx] = 'b';
          s[j] = 'a';
          // b_idx.pop_back();
          // b_idx.push_back(idx);
          // a_idx.pop_back();
          b_idx.erase(--b_idx.end());
          b_idx.insert(idx);
          a_idx.erase(--a_idx.end());
          a_idx.erase(a_idx.begin());
          ret += abs(j - idx);
          // cout << "switch 2: " << idx << " " << j << "\n";
        }
        // idx = a_idx.back();
        // a_idx.pop_back();
        // a_idx.pop_front();
        // s[idx] = 'b';
        // s[n - i - 1] = 'a';
        // ret += abs((n - i - 1) - idx);
      } else {
        if (abs(i - *a_idx.begin()) < abs(j - *b_idx.rbegin())) {
          int idx = *a_idx.begin();
          s[idx] = 'b';
          s[i] = 'a';
          // b_idx.pop_front();
          // b_idx.push_front(idx);
          // a_idx.pop_front();
          b_idx.erase(b_idx.begin());
          b_idx.insert(idx);
          a_idx.erase(a_idx.begin());
          a_idx.erase(--a_idx.end());
          ret += abs(i - idx);
          // cout << "switch 3: " << idx << " " << i << "\n";
        } else {
          int idx = *b_idx.rbegin();
          s[idx] = 'a';
          s[j] = 'b';
          // a_idx.pop_back();
          // a_idx.push_back(idx);
          // b_idx.pop_back();
          a_idx.erase(--a_idx.end());
          a_idx.insert(idx);
          b_idx.erase(--b_idx.end());
          b_idx.erase(b_idx.begin());
          ret += abs(j - idx);
          // cout << "switch 4: " << idx << " " << j << "\n";
        }
        // idx = a_idx.front();
        // a_idx.pop_front();
        // s[idx] = 'b';
        // s[i] = 'a';
        // // cout << "switch " << idx << " " << i << "\n";
        // ret += abs(idx - i);
      }
    } else if (s[i] == 'a') {
      // a_idx.pop_front();
      // a_idx.pop_back();
      a_idx.erase(a_idx.begin());
      a_idx.erase(--a_idx.end());
    } else if (s[i] == 'b') {
      // b_idx.pop_front();
      // b_idx.pop_back();
      b_idx.erase(b_idx.begin());
      b_idx.erase(--b_idx.end());
    }
  }
  // cout << s << "\n";
  cout << ret << "\n";
}