Longest palindromic subsequence

Not to be confused with Longest palindromic substring.

The longest palindromic subsequence problem is the problem of finding the longest subsequence of a string (a subsequence is obtained by deleting some of the characters from a string without reordering the remaining characters) which is also a palindrome. In general, the longest palindromic subsequence is not unique. For example, the string alfalfa has two palindromic subsequences of length 5: alala and afafa. However, it does not have any palindromic subsequences longer than five characters. Therefore alala and afafa are both considred longest palindromic subsequences of alfalfa.

Precise statement

Three variations of this problem may be distinguished:

• Find the maximum possible length for a palindromic subsequence.
• Find some palindromic subsequence of maximal length.
• Find all longest palindromic subsequences.

Theorem: Returning all longest palindromic subsequences cannot be accomplished in worst-case polynomial time.

Proof: Consider a string made up of $N/2$ ones, followed by $N/4$ zeroes, and finally $N/4$ ones. (Assume $N$ is a multiple of 4, although it does not really matter.) Any palindromic substring either does not contain any zeroes, in which case its length is only up to $3N/4$, or it contains at least one zero. If it contains at least one zero, it must be of the form $1^a0^b1^c$, but $a$ and $c$ must be equal. (This is because the middle of the palindrome must lie somewhere within the zeroes, otherwise there would be no zeroes on one side of it and at least one zero on the other side; but as long as the middle lies within the zeroes, there must be an equal number of ones on each side.) But $c$ can only be up to $N/4$, and likewise with $b$, so again the palindrome cannot be longer than $3N/4$ characters. However, there are $\binom{N/2}{N/4}+1$ palindromic substrings of length $3N/4$; we can either take all the ones, or we can take all $N/4$ zeroes, all $N/4$ terminal ones, and $N/4$ out of the $N/2$ initial ones. Thus the output size is not polynomial in $N$, and then neither can the algorithm be in the worst case. $_\blacksquare$

However, this does not rule out the existence of a polynomial-time algorithm for the first two variations on the problem. We now present such an algorithm.

Algorithm

todo

External links

• IOI '00 - Palindrome
• SPOJ:
  • Palindrome 2000 (a duplicate of the problem above)
  • Aibohphobia