Author : Kamonasish Roy
Tester : Abu Sufian Rafi, Abid Hussen, Emon Thakur
Editorial : A valid rearrangement exists if and only if the maximum character frequency maxf satisfies
maxf ≤ ⌈n/2⌉. where n is the length of string.
If maxf > ⌈n/2⌉, there aren’t enough other letters to separate the repeats, so answer = –1.

Compute total remaining letters total = n.

Initialize prev = '\0' (meaning “no previous character”).

For positions i = 1…n:

total remaining before placing = total.

Compute maxf = max_c freq[c].

Force‑pick test:

After you place one letter, there will be total – 1 slots left.

If maxf > (total – 1), then you must place a letter ∗c with freq[c*] = maxf here—otherwise in the remaining slots those copies would have to sit adjacent.

Scan c from 'a' to 'z', skip any with freq[c]==0 or c==prev, and choose the smallest such c.

Place that letter c at position i.

Decrement freq[c]--.

Decrement total--.

Set prev = c.

If you fill all n positions successfully, print the constructed string.

Time Complexity:
Each of n positions checks at most 26 letters and tracks frequencies in O(1), for O(n·26) overall.

Code ( C++) :

#include<bits/stdc++.h>
using namespace std;
const long long M=1e6+1,MOD=1e9+7;
typedef long long ll;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
   
    cin>>t;
    while(t--){
    	string s;
    	cin>>s;
    	int n=(int)s.size();
    	vector<int>fre(26,0);
    	for(int i=0;i<n;i++)fre[s[i]-'a']++;
    	int cur=0;
    	for(int i=0;i<26;i++)cur=max(cur,fre[i]);
    	int rem=n-cur;
    	if(cur-rem>1){
    		cout<<-1<<"\n";
    		continue;
    	}
    	vector<int>res(n+2,-1);
    	int baki=n;
    	for(int i=1;i<=n;i++){
    		int cur_mx=0;
    		for(int j=0;j<26;j++)cur_mx=max(cur_mx,fre[j]);
    		rem=baki-cur_mx;
    		if(cur_mx>rem){
    			for(int j=0;j<26;j++){
    				if(fre[j]==cur_mx){
    					res[i]=j;
    					fre[j]--;
    					break;
    				}
    			}
    		}
    		else{
    			for(int j=0;j<26;j++){
    				if(fre[j] && res[i-1]!=j){
    					res[i]=j;
    					fre[j]--;
    					break;
    				}
    			}
    		}
    		baki--;
    	}
    	for(int i=1;i<=n;i++)cout<<(char)('a'+res[i]);
    	cout<<"\n";
    	
    	}
    	
    	   
    return 0;
 
}