# Fastest algorithm for finding the longest palindrome subsequence

First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the answer is 7 ("abababa").

Postscript: the size of the word is smaller than 3000.

## migrated from math.stackexchange.comJun 24 '12 at 6:17

This question came from our site for people studying math at any level and professionals in related fields.

• By max palindrome do you mean you can delete characters from the string to leave a palindrome, and you want the longest palindrome (or minimum removal)? – Ross Millikan Jun 18 '12 at 14:24
• In your example, there is also cababac of length 7. The removed characters are then next to each other and on the end. Are you allowed either of these restrictions? They simplify the search greatly. – Ross Millikan Jun 18 '12 at 14:26
• This was already answered on Stack Overflow: how to find longest palindromic subsequence? – Generic Human Jun 18 '12 at 14:33
• @GenericHuman: The best answer in that question was good for the chapter of the textbook that the asker was reading. It's not a good answer for this asker. See this question: stackoverflow.com/questions/7043778/… instead. – Neil G Jun 23 '12 at 5:44
• How is the size used? You say you want the "max palindrome", so what if the longest palindrom is longer or shorter than the given size? – Gilles 'SO- stop being evil' Jun 24 '12 at 8:13

There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.

Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.

Edit

I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the longest palindrome subsequence of a string, so dynamic programming seems good: \begin{align*} f_{j,k}&=\max(f_{j,k+1},f_{j+1,k},2[S_j=S_k]+f_{j+1,k-1}),\qquad j<k\\ f_{k,k}&=1\\ f_{j,k}&=0,\qquad j>k\\ \end{align*} where $f_{j,k}$ denotes the length of the longgest palindrome subsequence of $S_{j..k}$, and $[P]$ is Iverson bracket I think it's just like LCS.

• You're answering in the substring case, but the question is about subsequences. – Generic Human Jun 23 '12 at 13:08
• Shouldn't the first term be f (j, k-1)? – Abhishek Bansal Sep 26 '14 at 14:20

The fastest algorithm I can think of is applying LCS in a creative way. It can solve this problem in O(N^2) time and O(N^2) space where N is the size of string.

LCS (S, reverse (S)) will give you the largest palindromic subsequence, as the largest palindromic subsequence will be the largest common subsequence between the string S and its reverse.

For example,
S = "abcababac"
T = "cababacba" (reverse of S)
LCS (S, T) = "abababa"

• Can you argue this algorithm is the fastest one anyone can come up with, as the question is asking? – Juho Mar 22 '13 at 21:18
• @Juho: I can't. :( This is the fastest algorithm I know of. It however was accepted at UVA online judge (uva.onlinejudge.org/external/114/11404.html) and in ACM the problem constraints are such that only the optimized solution will pass. Hence the solution is fast enough, not sure about the fastest. – Shashwat Mar 22 '13 at 21:31

Problem of finding LPS of a string can be converted into finding Longest Common Subsequence of two strings. In this, one string will be original one and the second will be reverse of the original string.

The Longest Common Subsequence problem is like the pattern matching problem, except that you are allowed to skip characters in the text. Also, the goal is to return just one match, which is as long as possible.

LCS can be solved in $O(n^2)$ using Recursion and Memoization.

There exists a slightly faster algorithm discovered by Masek and Paterson of time complexity $O(n^2/\lg n)$. Paper link: Masek and Paterson

Two other algorithms presented by Hirschberg to compute LCS of two strings $A$ (size $n$) and $B$ (size $m$). Based on the assumption that the symbols that may appear in these strings come from some alphabet of size $t$ (that is actually true in most of the cases). So symbols can be stored in memory using $\log(t)$ bits, which will fit in one word of memory. two symbols can be compared in $O(1)$ time. Number of different in string $B$ is denoted by $s$, which is of-course less than both $m$ and $t$.

1. This one requires $O(pn + n\lg n)$ time where $p$ is the length of LCS. This is used when length of LCS is expected to be small. When we solve this the problem using Dynamic Programming then we encounter that most of the entries in the matrix are same, so we can use the idea of Sparse Dynamic Programming.

2. This algorithm requires $O(p(m+1-p)\log n)$ time. This is very efficient when length of LCS is close to $m$, in that case it will be close to $O(n \lg n)$.

Detailed procedures and algorithms are explained in the Hirschberg's paper.

An another good algorithm is proposed by Sohel Rahman that runs in $O(R \log\log n)$ time, where $R$ is the total number of ordered pairs of positions at which to strings match. It is not applicable when $R$ is the order of $O(n^2)$, but there are many cases when $R$ is the order of $n$. This one uses the concept RMQ (Range Maximum Query). Paper link: Rahman

• @FrankW, thanks! I have edited the answer. Now links are visible. – Surendra Sep 26 '14 at 12:58
• Your formatting was still lacking; please check my edit to see what's possible. The article references are still bad because they rely on the link always working, forever. See here for advice; title, authors and year should be given (at least). – Raphael Sep 26 '14 at 13:02
• Two concerns with what you write: 1) "requires $O(\dots)$" is meaningless (since $O$ gives upper bounds), and ignoring that probably wrong; I'd guess they show upper bounds of these orders but the algorithms may be faster even. 2) In the last paragraph at least, you want $\Omega(n^2)$. – Raphael Sep 26 '14 at 13:04

I'm probably missing something, because it seems rather trivial to me: Try to pair each character with an equal character. Then put the first character of each pair on the left side, the other character on the right side, and if there are any characters remaining (ie, characters not paired with another one), then pick one of them and put that one in the middle.

• When you have $aubvawb$ (with $u,v,w$ words), how would you decide if the first and last character of the palindrome should be $a$ or $b$? You need to examine the contents of $u,v,w$ before you make a decision if you want to have the longest palindrome. – Generic Human Jun 23 '12 at 14:55