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
#include <bits/stdc++.h>

using namespace std;

void solve_test_case();

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve_test_case();
}

void solve_test_case()
{
  string word;
  cin >> word;

  vector<bool> W(word.size());
  for (size_t i = 0; i < word.size(); i++) W[i] = word[i] == 'b';

  set<size_t> indices[2];
  for (size_t i = 0; i < W.size(); i++) indices[W[i]].insert(i);

  if (indices[0].size() % 2 == 1 && indices[1].size() % 2 == 1)
  {
    cout << "-1 \n";
    return;
  }

  size_t swaps = 0;
  for (size_t i = 0; 2 * (i + 1) < W.size(); i++)
  {
    size_t j = W.size() - i - 1;

    bool left = W[i];
    bool right = W[j];

    if (left == right)
    {
      indices[left].erase(i);
      indices[right].erase(j);
    }
    else if (indices[left].size() == 1)
    {
      swap(W[i], W[i + 1]);
      indices[left].erase(i);
      indices[left].insert(i + 1);
      indices[right].erase(i + 1);
      if (i + 1 != j) indices[right].erase(j);
      swaps++;
    }
    else if (indices[right].size() == 1)
    {
      swap(W[j - 1], W[j]);
      indices[right].erase(j);
      indices[right].insert(j - 1);
      indices[left].erase(j - 1);
      if (j - 1 != i) indices[left].erase(i);
      swaps++;
    }
    else
    {
      auto match_left = *(indices[left].rbegin());
      auto match_right = *(indices[right].begin());

      if (j - match_left <= match_right - i)
      {
        swap(W[j], W[match_left]);
        indices[left].erase(i);
        indices[left].erase(match_left);

        indices[right].erase(j);
        indices[right].insert(match_left);
        swaps += j - match_left;
      }
      else
      {
        swap(W[i], W[match_right]);
        indices[right].erase(j);
        indices[right].erase(match_right);

        indices[left].erase(i);
        indices[left].insert(match_right);
        swaps += match_right - i;
      }
    }
  }

  cout << swaps << "\n";
}