Palindrome Reorder

Given a string, your task is to reorder its letters in such a way that it becomes a palindrome (i.e., it reads the same forwards and backward).

Example:

Input:  s = "AAAACACBA"
Output: AAACBCAAA

Approach

Java

public class PalindromeReorder {
    public static void main(String[] args) {
        String s = "AAAACACBA";

        palindromeReorder(s);

    }

    static void palindromeReorder(String s) {

        int f[] = new int[26];
        for (int i = 0; i < s.length(); i++)
            f[s.charAt(i) - 'A']++;

        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (f[i] % 2 == 1)
                cnt++;
        }
        if (cnt > 1)
            System.out.println("NO SOLUTION");
        else {

            char[] res = new char[s.length()];
            int m = 0;
            int flag = 0;
            int l = 0, k = s.length() - 1;
            for (int i = 0; i < 26; i++) {
                if (f[i] % 2 == 0) {
                    int x = f[i] / 2;
                    int x1 = f[i] / 2;
                    while (x > 0) {
                        res[l++] = (char) (i + 'A');
                        x--;
                    }

                    while (x1 > 0) {
                        res[k--] = (char) (i + 'A');
                        x1--;
                    }
                } else {
                    flag = 1;
                    m = i;
                }
            }
            if (flag == 0)
                System.out.println(res);
            else {
                for (int j = l;; j++) {
                    res[j] = (char) (m + 'A');
                    f[m]--;
                    if (f[m] == 0)
                        break;
                }
                System.out.println(res);
            }
        }
    }

}

C++

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

void palindromeReorder(string s)
{

    int f[26] = {0};
    for (int i = 0; i < s.size(); i++)
        f[s[i] - 'A']++;
    string res;
    int cnt = 0;
    for (int i = 0; i < 26; i++)
    {
        if (f[i] & 1)
            cnt++;
    }
    if (cnt > 1)
        cout << "NO SOLUTION\n";
    else
    {

        res.resize(s.size());
        int m = 0;
        int flag = 0;
        int l = 0, k = s.size() - 1;
        for (int i = 0; i < 26; i++)
        {
            if (f[i] % 2 == 0)
            {
                int x = f[i] / 2;
                int x1 = f[i] / 2;
                while (x--)
                    res[l++] = i + 'A';
                while (x1--)
                    res[k--] = i + 'A';
            }
            else
            {
                flag = 1;
                m = i;
            }
        }
        if (flag == 0)
            cout << res << "\n";
        else
        {
            for (int j = l;; j++)
            {
                res[j] = m + 'A';
                f[m]--;
                if (f[m] == 0)
                    break;
            }
            cout << res << "\n";
        }
    }
}
int main()
{
    string s = "AAAACACBA";

    palindromeReorder(s);

    return 0;
}