Solução escrita por Arthur Lobo
Conhecimento prévio necessário:
Primeiro vamos pensar no caso mais simples: quando o tamanho da string (vamos chamar de 
) é par.
Quando é par e é possível formar um palíndromo, a primeira metade da string é exatamente igual a segunda metade invertida, então com certeza a quantidade de vezes (frequência) que cada caractere aparece é par - dizemos que essa é uma condição necessária, ou seja, que deve acontecer para que seja possível transformar a string em palíndromo, mas será que também é suficiente?
Se a frequência de cada letra é par, então podemos montar o palíndromo inserindo essa letra alternadamente no início e no fim, fazendo com que no final seja um palíndromo e usemos todas as letras disponíveis, portanto, essa condição também é suficiente, ou seja, se ela acontece, então é possível transformar a string em palíndromo.
Quando uma condição é necessária e suficiente, nós precisamos apenas checá-la para saber se é ou não possível! Então já sabemos resolver para o caso par: podemos usar uma estrutura como o deque, que permite inserção no início e no final, e vamos inserindo cada letra em ambos os lados do deque enquanto ainda podemos fazer isso.
Para o caso em que é ímpar é só perceber que a condição se transforma em "todas as letras aparecem uma quantidade par de vezes, menos uma, que aparece uma quantidade ímpar". Essa letra que vai aparecer uma quantidade ímpar vai ser a que fica exatamente no meio. É fácil ver que não podemos ter 0 ímpares (pois a soma é ímpar), e se tivermos mais que 1 ímpar é impossível.
Para montar o caso ímpar, basta colocar a letra ímpar no início do deque e resolver para o caso par.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.