Shil and Palindrome

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​​.

Example:

Input:  s = "aabcc"
Output: acbca

Approach

C++

#include <bits/stdc++.h>
using namespace std;

void shilAndPalindrome(string s)
{
    int n = s.size();
    int f[26] = {0};
    for (int i = 0; i < n; i++)
        f[s[i] - 'a']++;
    int cnto = 0, cnte = 0;
    sort(s.begin(), s.end());
    for (int i = 0; i < 26; i++)
    {
        if (f[i] > 0 && f[i] & 1)
            cnto++;
        else if (f[i] > 0 && f[i] % 2 == 0)
            cnte++;
    }
    if (cnto == 0 && n & 1)
        cout << -1 << "\n";
    else if (n % 2 == 0 && cnto > 0)
        cout << -1 << "\n";
    else
    {
        char str[n + 1];
        int i = 0;
        int l = 0, j = n - 1;
        while (i < n)
        {
            if ((i < n - 1) && (s[i] == s[i + 1]))
            {
                str[l] = s[i];
                str[j] = s[i + 1];
                i += 2;
                l++;
                j--;
            }
            else
            {
                str[n / 2] = s[i];
                i++;
            }
        }
        string res = "";
        for (int i = 0; i < n; i++)
            res += str[i];
        cout << res << "\n";
    }
}
int main()
{

    string s = "aabcc";

    shilAndPalindrome(s);

    return 0;
}