链接：https://ac.nowcoder.com/acm/contest/92662/E
来源：牛客网

拿到了一个仅由小写字母组成的字符串，她希望你能重排这个字符串，使得每个对应位置的字符和重排前都不相同。

设最大同种字符数量为m，若m>n/2则无解。
若m<n/2。如果字符串排序，容易构造一种方案：将整个字符串循环右移m次。

因此将字符串排序，并记录排序前后下标的对应关系idx。然后对每个位置右移m次，再通过idx映射回原数组，修改原数组对应位置的字符。

#include<bits/stdc++.h>
#define LOCAL
using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

void solve(){
    string s;
    cin>>s;
    int n = s.size();
    vector<pair<char,int>> val;
    vector<int> idx(n+1);
    vector<int> cnt(40);
    int mx = 0;
    for(int i=0;i<n;i++){
        val.push_back({s[i],i});
        cnt[s[i]-'a']++;
        if(cnt[s[i]-'a']>mx) mx = cnt[s[i]-'a'];
    }

    if(mx > n/2) return cout<<"-1"<<endl,void();

    sort(val.begin(),val.end());
    for(int i=0;i<n;i++){
        idx[i] = val[i].second; 
    }
    string ans(n,' ');
    for(int i=0;i<n;i++){
        auto [c,id] = val[i];
        int nid = (i+mx)%n;
        ans[idx[nid]] = c;
    }
    cout<<ans<<endl;
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }

    return 0;
}