Dynamic Programming — Longest Palindromic Subsequence

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.
Longest Palindromic Subsequence Example

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(2n).

We can do it better by solving this problem using Dynamic Programming.

Dynamic Programming:

Optimal Substructure:

Given Sequence A[0….n-1]

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

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.

Longest Palindromic Subsequence - 2

 

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.

Longest Palindromic Subsequence - Overlapping Subproblems

Longest Palindromic Subsequence – Overlapping Subproblems

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
LPS[i, j] = 2 if j=i+1, sequence has only 2 characters
LPS[i, j] = 2 + LPS[i-1, j-1] If first and last characters are same
LPS[i, j] = MAX(LPS[i+1,j], LPS[i, j-1]) If first and last characters are not same

 

Code:

Output: 

1 2 2 2 2 2 3 5 5
0 1 1 1 1 1 3 5 5
0 0 1 1 1 1 3 3 3
0 0 0 1 1 1 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 1 1 1

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

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

  • Nguyen Hoang Nam

    Hello, I’ve another way to solve this problem, but i don’t know it can be called Dynamic Programming or not. Here is my code in java: https://gist.github.com/nhnpro/fd6f3c4052658ecca34155d7c46382f8

    Thanks

  • Jon Roetman

    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’

%d bloggers like this: