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.
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.
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 .
- 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.
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
|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|
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