字符串重排问题

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

一个仅由小写字母组成的字符串。长度不超过$10^5$。

如果无解，请输出-1。
否则输出任意合法字符串。

输入

aba

aba```输出
--\-1

-1```
输入

abbc

abbc```输出
--bcab

bcab```

说明

思路：对于这种问题，我们很容易的判断不行的情况是有一种字母 * 2 大于总的数量，然后我们将所有的存到一个二元组内，first代表字符，second代表位置，然后我们根据字符进行排序，将相同的字符排在一起，我们同时偏移maxs最后所生成的答案就是符合的。也是一个小结论吧

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 1e9 + 7;
const int MOD = 998244353;
typedef long long ll;
typedef pair<ll,ll>PII;
typedef pair<char, int>PCI;
//字符串偏移maxs即可
PCI p[N];
char c[N];
int main()
{map<char, vector<int>>ma;string s;cin >> s;int n = s.size(), maxs = 0;for(int i = 0; i < n; i ++){ma[s[i]].push_back(i);p[i] = {s[i], i};maxs = max((int)ma[s[i]].size(), maxs);}if(maxs * 2 >= n) cout << -1 << endl;else {sort(p, p + n);//开始偏移for(int i = 0; i < n; i ++){c[p[i].second] = p[(i + maxs) % n].first;}for(int i = 0; i < n; i ++) cout << c[i];}return 0;
}