Objective: Given a string, find a longest palindromic subsequence in it.

What is Longest Palindromic Subsequence: A longest palindromic subsequence is a sequence that appears in the same relative order, but not necessarily contiguous(not substring) and palindrome in nature( means the subsequence will read same from the front and back.

Example:
String A = " AABCDEBAZ";
Longest Palindromic subsequence: ABCBA or ABDBA or ABEBA
There are many subsequences can be found which are palindrome like, AA, BCB, ABA, BB etc but we need to find the one with the maximum length.

Approach:

Recursion:

Check every subsequence of in a given string, which means every character as two options, whether it will be included in the subsequence or it will be excluded. If we do it by recursion which means all the sub problems will be solved repeatedly that means Time Complexity will be O(2^{n}).

LPS[0….n-1] be the longest palindromic subsequence of the given sequence.

Check the first and the last characters of the sequence. Now there are two possibilities, either both the characters same or distinct. We will have to handle both the case.

If both characters are same, add 2 to the result and remove both the characters and solve the problem for the remaining subsequence .

Longest Palindromic Subsequence – 1

If both characters are different, then solve the problem twice, ignore the first character (keep the last character)and solve the remaining subsequence and then ignore the last character (keep the first character) and solve it and pick the best out of two results.

Overlapping Subproblems:

Say given input string: ABCDE

If we solve it recursively, look at the recursion tree, we will be solving the sub-problems repeatedly.

So while using the dynamic programming, we will solve it in bottom-up manner and store the results of sub-problems once we solve them for future reference. See the code for the better explanation

Recursive Equations:

LPS[i, i]

=

1

Every single character is a palindrome by itself of length 1

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Unless I’m missing something here, isn’t the example’s (AABCDEBAZ) longest palindromic subsequence “AA”, which is 2? It seems the output indicates 5….

Prashant Kumar

thnks !! great explanation

robinfrmrome

Hi,

In the above code. Consider the following scenario

String: abca
i = 0
j = 3

Then the result would 2 which is incorrect. It should rather be 1.

Please explain/correct me if I am wrong.

Thank You.

tutorialhorizon

Hello Robin, I think you are confusing this problem with longest palindromic substring, its a sub sequence. so answer to your example would be 3 not 1. and longest sequence would be either ‘aba’ or ‘aca’