Palíndromo
Dado una cadena S de letras mayúsculas, se te permite realizar cualquier cantidad (incluyendo 0) de las siguientes operaciones (y en el orden que desees):
- Borrar una letra de cualquier posición
- Intercambiar dos letras en posiciones adyacentes
¿Cuál es el palíndromo más largo que puedes formar?
Un palíndromo es una cadena de caracteres que se lee igual de izquierda a derecha como de derecha a izquierda.
Entrada
La primera línea de entrada consiste en un solo número entero \(T (1 \le T \le 100)\) indicando el número de casos de prueba a procesar.
Cada caso de prueba consiste en dos líneas:
- Línea 1 contiene un solo número entero \(N (1 \le N \le 1000)\), que representa la longitud de la cadena
.
- Línea 2 consiste en la cadena
letras, todas en mayúsculas.
Salida
Por cada caso de prueba, en el mismo orden dado por la entrada, imprime el palíndromo más largo que puedes obtener luego de aplicar cualquier cantidad de las operaciones descritas. Si existen varios palíndromos que cumplen con las condiciones dadas, imprime el más pequeño en orden lexicográfico. Una cadena es lexicográficamente más pequeño que otra cadena T si el caracter en la posición i de S es más pequeño que el caracter en la misma posición i de T donde i es la primera posición donde las dos cadenas difieren.
Ejemplo de entrada
4
4
NOON
5
MADAM
3
ABC
8
XXXZZZYYEjemplo de salida
NOON
AMDMA
A
XYZXZYX
Comments
Comentaré mi solución-idea, alerta de spoiler:
Como sabemos que un palíndromo es una cadena que se lee igual de izquierda a derecha que de derecha a izquierda, esto significa también que los caracteres de la cadena deben ser simétricos respecto al centro de la misma. O sea, si la cadena tiene una longitud par, los caracteres deben aparecer en pares iguales a ambos lados del centro, pero si la cadena tiene una longitud impar, los caracteres deben aparecer en pares iguales a ambos lados del centro, excepto uno que puede aparecer solo en el centro. Puedes comprobarlo rápidamente escribiendo una que otra cadena palíndrome.
Por ejemplo, la cadena
es un palíndromo de longitud par 
, y los caracteres 
y 
aparecen en pares iguales a ambos lados del centro. La cadena 
es un palíndromo de longitud impar, y los caracteres 
y 
aparecen en pares iguales a ambos lados del centro, pero eso sí, el carácter 
aparece solo en el centro.
Esto nos da una pista de cómo construir el palíndromo más largo que se puede formar: usar la mayor cantidad posible de caracteres que aparezcan un número par de veces en la cadena, y si hay algún carácter que aparezca un número impar de veces, podemos usar uno de ellos en el centro. Para ello se debe contar la frecuencia de cada carácter en la cadena, y ya luego usar la mitad de cada carácter que tenga una frecuencia par, y uno de los caracteres que tenga una frecuencia impar, si es que existe. El orden de los caracteres no importa, siempre que se mantenga la simetría, pero si queremos el palíndromo más pequeño en orden lexicográfico, debemos usar los caracteres en orden alfabético.
Esto es Hashing????
No es necesario, fíjate que como te permiten cambiar el orden de las letras al final lo importante es cuántas veces se repite cada letra. En una palabra palindrome hay a lo sumo una letra que se repite una cantidad Impar de veces, (esto solo pasa en caso de q la palabra palindrome sea de longitud impar). Ya con esto puedes llegar a la solución fácilmente.