A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence
has many palindromic subsequences, including
A,A,A,A(on the other hand, the subsequence
A,C,Tis not palindromic). Devise an algorithm that takes a sequence
x[1 ...n]and returns the (length of the) longest palindromic subsequence. Its running time should be
This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in
Firstly, the empty string and a single character string is trivially a palindrome.
Notice that for a substring
This gives us the function:
You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.
This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.
This problem can also be done as a variation of a very common problem called the LCS(Longest Common sub sequence) problem. Let the input string be represented by a character array s1[0...n-1].
1) Reverse the given sequence and store the reverse in another array say s2[0..n-1] which in essence is s1[n-1....0]
2) LCS of the given sequence s1 and reverse sequence s2 will be the longest palindromic sequence.
This solution is also a O(n^2) solution.
Working Java Implementation of Longest Palindrome Sequence
It makes me a little confused that the difference between substring and subsequence.(See Ex6.8 and 6.11) According to our comprehension of subsequence, the giving example doesn't have the palindromic subsequence ACGCA. Here's my pseudo code, I'm not quite sure about the initialization ><
preparing for the algorithm final...
This can be solved in O(n) very simply. A palindrome can have any number of letters which appear an even number of times, but at most one letter which appears an odd number of times.
If you can choose which letters to use, add all the letters (to the start and end) which appear an even number of times and add a letter which occurs an odd number of times to the center.
You can do this with two passes, first to count the number of occurences, the second to build the string.
for each letter in the string:
O(N^2) : since we have one loop that choose the middle and one loop that check how long the palindrome if this is the middle. each loop runs from 0 to O(N) [the first one from 0 to N-1 and the second one is from 0 to (N-1)/2]
for example: D B A B C B A
i=0 : D is the middle of the palindrome, can't be longer than 1 (since it's the first one)
i=1: B is the middle of the palindrome, check char before and after B : not identical (D in one side and A in the other) --> length is 1.
i=2 : A is middle of the palindrome, check char before and after A : both B --> length is 3. check chars with gap of 2: not identiacl (D in one side and C in the other) --> length is 3.
Input : A1,A2,....,An
Goal : Find the longest strictly increasing subsequence (not necessarily contiguous).
L(j): Longest strictly increasing subsequence ending at j
You will get the source code here