Игра в слова

#include<bits/stdc++.h>

using namespace std;

bool cmp(vector<int> &a, vector<int> &b)
{
    return a.size() > b.size();
}

main()
{
    int q;
    cin >> q;
    while(q--)
    {
        string s;
        cin >> s;
        int n = s.size();
        string was = s;
        vector<vector<int>> v('z' - 'a' + 1, vector<int>());
        for(int i = 0; i < n; i++)
            v[s[i] - 'a'].push_back(i);
        bool f = 0;
        for(auto i : v)
        {
            if(i.size() > n / 2)
            {
                cout << -1 << "\n";
                f = 1;
                break;
            }
        }
        if(f)
            continue;
        sort(v.begin(), v.end(), cmp);
        while(v.back().empty())
            v.pop_back();
        int l = 0, r = v.size() - 1;
        while(true)
        {
            if(v[l].empty())
                l++;
            if(v[r].empty())
                r--;
            if(l >= r)
                break;
            swap(s[v[l].back()], s[v[r].back()]);
            v[l].pop_back();
            v[r].pop_back();
        }
        vector<int> o, c;
        for(int i = 0; i < n; i++)
            if(was[i] == s[i])
                o.push_back(i);
            else
                c.push_back(i);
        for(int i = 0; i < o.size(); i++)
            swap(s[o[i]], s[c[i]]);
        cout << s << "\n";
    }
}