Palindrome.cpp

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

int freq[30]; // vetor que vai guardar a frequencia de cada letra

int32_t main() {
    string s;
    cin >> s;
    int n = s.size();

    for(int i = 0; i < n; i++) {
        freq[s[i]-'A']++;
    }

    deque<char> resp;
    int letra_impar = -1;
    for(int i = 'A'-'A'; i <= 'Z'-'A'; i++) {
        if(freq[i]%2 == 1) {
            if(letra_impar != -1 || n%2 == 0) {
                cout << "NO SOLUTION" << endl;
                return 0;
            }
            else {
                letra_impar = i;
            }
        }
    }

    if(n%2 == 1) {
        resp.push_back((char) (letra_impar+'A'));
        freq[letra_impar]--;
    }

    for(int i = 'A'-'A'; i <= 'Z'-'A'; i++) {
        while(freq[i] != 0) {
            resp.push_back((char) (i+'A'));
            resp.push_front((char) (i+'A'));
            freq[i]-= 2;
        }
    }

    for(int i = 0; i < resp.size(); i++) {
        cout << resp[i];
    }
    cout << endl;

}