Devu and decorating birthday cake
 |
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Today is Devu's birthday. He has obtained few colored balloons from his friends. You are given this information by a string s consisting of lower case English Latin letters. Each letter (from 'a' to 'z') denotes a color. e.g. if s = "aab", then it means that he has received two balloons of color 'a' whereas one balloon of color 'b'.
Now, Devu wants to decorate the cake by arranging all the balloons linearly from left to right on the cake such that no same colored balloons are nearby/ adjacent to each other.
Now Devu wonders whether it is possible to do so or not? Please help him in this. If it is not possible to do so, print -1. Otherwise, print any one of arrangements of the balloons on the cake. If there are more than one possible ways of doing so, you can print any one of them.
Input
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- First line of each test case will contain string s
Output
Print a single line corresponding to the answer of the problem.
Constraints
- 1 ≤ T ≤ 105
- 1 ≤ size of string s ≤ 105
- Sum of size of string s over all test cases will be less than or equal to ≤ 106
Example
Input: 3 aab ab aa Output: aba ab -1
Explanation
Example case 1. He can arrange the balloons in the order given by the following string "aba".
Example case 2. He can arrange the balloons in the order given by the following string "ab"
Example case 3. There is no valid way of decorating cakes with balloon in the desired way. So we print -1.
/**********************************************************editorial*******************************************************
count hash of all ballons and check for the possiblity of answer ..
if ballon with colour having maximum count is greater than half of rest all ballons (in case of even no of ballons ) OR if no total ballon is odd than maximu>rest/2+1 than answer not exit ..
else
recunstruct an array which consist of ballons according to frequency -- ex aabbbbbccc will be recunstructed as bbbbbcccaa ..
now contruct ans array whic contain 1 element from start ie index 0 and next from middle , ie.
0th index, mid index ,1st index ,mid+1 index 2 nd index ,mid+2 index and so on .....
*******************************************code**************************************************************************
#include<iostream>
using namespace std;
char arr[1000000];
char ans[1000000];
#include<bits/stdc++.h>
int main()
{
long long int t;
cin>>t;
while(t--)
{
long long int n;
cin>>arr;
long long int len=strlen(arr);
//sort(arr,arr+len);
long long int sum=0;
long long int has[28];
vector<pair<int,int> >v;
for(int i=0;i<=27;i++) has[i]=0;
for(int i=0;i<len;i++)
{
has[arr[i]-'a']++;
}
for(int i=0;i<26;i++)
{
v.push_back(make_pair(has[i],i));
}
sort(has,has+26);
sort(v.begin(),v.end());
int top=0;
vector<pair<int,int> > ::iterator it;
for( it=v.end();it>=v.begin();it--)
{
int c=it->first;
// cout<<"c is "<<c<<endl;
for(int j=0;j<c;j++)
{
arr[top]=it->second+'a';
top++;
}
}
for(int i=0;i<25;i++) sum+=has[i];
if(len%2==1 && has[25]-sum>1)
cout<<"-1"<<endl;
else if(len%2==0 && has[25]-sum>0)
{
cout<<"-1"<<endl;
}
else
{
long long int mid=0;
if(len%2==1)
{
mid=(len/2)+1;
}
else mid=len/2;
long long int j=mid;
long long int tv=-1;
for(long long int i=0;i<mid;i++,j++)
{
ans[++tv]=arr[i];
ans[++tv]=arr[j];
}
for(long long int i=0;i<len;i++)
cout<<ans[i];
cout<<endl;
}
}
return 0;
}
