1st year CS engineering | birthday baloon output | cpp question

 Today is Sinu'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, Sinu 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 Sinu wonders whether it is possible to do so or not? Please help him by writing a program . 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

/**********************************************************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;

 }