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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <unordered_map>
#include <cassert>
#include <numeric>
#include <queue>


using namespace std;
#define LL long long

void convert_to_vector(const string& s, vector<char> &v)
{
    v.resize(s.size());
    for (int i=0; i < s.size(); i++)
    {
        v[i] = s[i]-'a';
    }
}

int next_index(const vector<char> &v, int idx, int limit, char ok_char, int step)
{
    while (idx != limit)
    {
        if (v[idx] == ok_char) break;
        if (step < 0 && idx <= limit) break;
        if (step > 0 && idx >= limit) break;
        idx += step;
    }
    return idx;
}

LL minimal_palindrom_fast(vector<char> &v) 
{
    LL res = 0;
    if (v.size() == 1) return 0;
    if (v.size() == 2) {
        if (v[0] == v[1]) return 0;
        else return -1;
    }
    const int L = 0;
    const int R = 1;
    const int N = v.size();
    int from[2][2] = {{-1,-1}, {N, N}};

    int start = 0, finish = N - 1;
    while (start < finish)
    {
        if (start + 1 >= finish) {
            break;
        }
        if (v[start] == v[finish]) {
            start++; finish--;
            //cout << "res=" << res << " letters match for start=" << start << ",finish=" << finish << "\n";
            continue;
        }
        for (int ci=0; ci < 2; ci++)
        {
            from[L][ci] = max(start, from[L][ci]);
            from[R][ci] = min(finish, from[R][ci]);
            from[L][ci] = next_index(v, from[L][ci], finish, ci, +1);
            from[R][ci] = next_index(v, from[R][ci],  start, ci, -1);
        }
        int first_different_idx_from_left = from[L][1-v[start]];
        int first_different_idx_from_right = from[R][1-v[finish]];

        int dist1 = first_different_idx_from_left - start;
        int dist2 = finish - first_different_idx_from_right;
        int med = -1;
        if (dist1 < dist2) {
            swap(v[start], v[first_different_idx_from_left]);
            med = first_different_idx_from_left;
            res += dist1;
        } else {
            swap(v[finish], v[first_different_idx_from_right]);
            med = first_different_idx_from_right;
            res += dist2;
        }
        assert (v[start] == v[finish]);
        from[L][v[med]] = min(from[L][v[med]], med);
        from[R][v[med]] = max(from[R][v[med]], med);
    }
    if ((start != finish) && v[start] != v[finish]) return -1;
    return res;
}

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

    string s; cin >> s;
    vector<char> v;
    convert_to_vector(s, v);
    cout << minimal_palindrom_fast(v);

    return 0;
}