This post is completed by 2 users

  • 1
 Add to List
Hard

175. 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]=1Every single character is a palindrome by itself of length 1
LPS[i, j]=2if 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

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

Related Problems: