In this HackerEarth Shil and Palindrome problem solution Shil is your new boss and he likes palindromes very much. A palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. (ex. madam, aabaa, racecar)

Given a string S, beautiful Palindrome is a lexicographical minimum palindrome that can be formed by rearranging all the characters of string S. In order to please your boss, find a beautiful Palindrome that can be formed with help of string S.

String x is lexicographically less than string y, if either x is a prefix of y (and x≠y), or there exists such i (1≤i≤min(|x|,|y|)), that xi<yi, and for any j (1≤j<i) xj=yj. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languages.


HackerEarth Shil and Palindrome problem solution


HackerEarth Shil and Palindrome problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long   int
#define INF 10000000
#define f first
#define pi pair<ll,ll>
#define pb emplace_back
#define mod 1000000007
#define s second
#define mp make_pair
#define fr freopen("input-15.txt","r",stdin)
#define fo freopen("output-15.txt","w",stdout)
int main(){
    string s;
    cin>>s;
    ll n=s.length();
    ll f[26]={0};
    string ans=string(n,'0');
    for(int i=0;i<s.length();i++) f[s[i]-'a']++;
    if(n%2==0){
        for(int i=0;i<26;i++){
            if(f[i]%2!=0){
                cout<<-1;
                return 0;
            }
        }
    }
    else{
        ll cnt=0;
        char c;
        for(int i=0;i<26;i++){
            if(f[i]%2!=0) cnt++,c=char(i+'a');
        }
        if(cnt!=1){
            cout<<-1;
            return 0;
        }
        ans[n/2]=c;
        f[c-'a']--;
    }
    ll j=0;
    for(int i=0;i<26;i++){
        while(f[i]>0){
            f[i]-=2;
            ans[j]=char(i+'a');
            ans[n-j-1]=char(i+'a');
            j++;
        }
    }
    cout<<ans;
}