Here’s my code for the problem it is giving correct answer for all the custom test input that I made
#include<bits/stdc++.h>
using namespace std;
/* author Geetesh Pandey*/
#define ll long long
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define max(a, b) (a < b ? b : a)
#define min(a, b) ((a > b) ? b : a)
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
void init_code()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
}
void solve()
{
string s;
cin>>s;
unordered_map<char,ll> mp;
map<char,vector<ll>> position;
ll n = s.size();
for(ll i=0;i<n;i++)
{
char temp = s[i];
mp[temp]++;
position[temp].push_back(i);
}
ll count = 0;
for(auto i:mp)
{
if(i.second % 2 == 1)
count++;
}
if(count>1)
{
cout<<-1<<endl;
return;
}
else
{
ll arr[n];
ll pos = 1;
for(auto i:position)
{
if(i.second.size() == 1)
{
arr[i.second[0]] = ceil((n+1)/2);
}
else
{
for(ll j = 0;j<i.second.size();j+=2)
{
arr[i.second[j]] = pos;
arr[i.second[j+1]] = (n- (pos-1));
pos++;
}
}
}
for(auto i:arr)
cout<<i<<" ";
cout<<endl;
}
}
int main()
{
clock_t start = clock();
init_code();
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
#ifndef ONLINE_JUDGE
clock_t end = clock();
cout << "\n\nExecuted in: " << (double)(end - start) / double(CLOCKS_PER_SEC)
<< " sec";
#endif
return 0;
}