Problema número 322

Tiro al patíndromo

Tiempo máximo: 1,000-3,000 sMemoria máxima: 10240 KiB

Ya es tradición que cuando en el pueblo de Juan Filloy* están en fiestas, él se pase por el puesto del tiro con escopeta. Cuando saben que va a visitarles, en vez de premios en los patos a los que hay que disparar colocan letras de tal forma que Juan pueda divertirse disparando a algunos de los patos de manera que se forme un palíndromo con las letras en los patos supervivientes (es decir, que al leer tanto de izquierda a derecha como de derecha a izquierda, se lea siempre la misma palabra). Por ejemplo, si se enfrentara a la serie de patos de la figura, Juan dispararía a los patos en las posiciones 1, 2 y 6, formando el palíndromo RODADOR.

Pato con una MPato con una EPato con una RPato con una OPato con una DPato con una EPato con una APato con una DPato con una OPato con una R
12345678910

Además, a Juan le gusta alardear ante las mozas del pueblo que le miran expectantes, por lo que no se conforma solamente con encontrar un palíndromo sino que lo intenta conseguir tirando el menor número de patos. En caso de empate, Juan prefiere tirar los patos de la izquierda, porque a la derecha le molesta más el Sol que le deslumbra. ¿Sabrías tú hacer lo mismo?

Entrada

La entrada estará compuesta por múltiples casos de prueba, cada uno en una línea. Cada caso consiste en una sucesión de un mínimo de 1 y un máximo de 1.000 letras mayúsculas del alfabeto inglés, sin símbolos especiales ni espacios.

Salida

Por cada caso de prueba se escribirá una línea que contenga el palíndromo más largo que puede formarse eliminando (si es necesario) algunas de las letras de la entrada. En caso de empate, se debe imitar a Juan, eliminando letras más a la izquierda.

Entrada de ejemplo

MERODEADOR
RECONOCER
ARADAROSOSOMI
OSORASODAR

Salida de ejemplo

RODADOR
RECONOCER
OSOSO
RADAR
1Escritor argentino nacido en 1894, autoproclamado "recordman mundial de palindromía", gracias al cual hoy conocemos más de 8.000 palíndromos en español.