3672 - Palindrome
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
- ymondelo20
- Posts: 1968
- Joined: 7 years ago
- Location: Universidad de las Ciencias Informáticas
- Gender:
- Contact:
Re: 3672 - Palindrome
Si se quiere obtener el mayor palindrome que es subsecuencia de una cadena dada, bastaria con realizar un LCS entre la cadena y ella misma, pero invertida. Como esto nos da la longitud del mayor palindrome que existe en la cadena, bastaria con restarle al total de caracteres de la cadena, la longitud del LCS antes mencionado, lo que representa la cantidad de caracteres que no pertenecen al palindrome y deben ser agregados para emparejar la situacion y formar un palindrome. En resumen, seria N - LCS(cadena, cadena_invertida)