Longest Palindromic Subsequence

Given a string, find a longest palin­dromic sub­se­quence in it.

Recursive Formula:

 If ith and jth characters are same then,
    2 + recursive call for (i +1) and (j -1)
 Else
    Max of {(recursive call of i, j-1 ) and (recursive call i+1, j)}

DP Formula:

If ith and jth characters are same then
   T[i][j] = 2 + T[i+1][j-1]
Else
   T[i][j] = Max {T[i+1][j],  T[i][j-1]}

Solution:

• Here we start work from sub string of length 1, 2, 3, ….. string.length.
• For string length 1, Longest Palindromic Subsequence is 1.
• Suppose for sub-string BABCB
  • Here first and last characters are equal
  • So, LPS = 2 + LPS(“ABC”)
  • But for sub-string BABCA
  • Here first and last characters are not equal,
  • So, LPS = Max {LPS(“BABC”), LPS(“ABCA”) },
  • i.e. for we will try to find LPS of length 4, if first and last character of string of length is not equal.

Dynamic Programming Algorithm:

1. Create dp table of (str.length) X (str.length)
2. Update table for substring length 1
3. Iterate substring length 2 to str.length
   1. Iterate all subStrings of length i
      1. If first and last character of substring is equal then
         1. Set table[subStringStartIndex][subStringEndIndex] = 2 + table[subStringStartIndex + 1][subStringEndIndex -1]
      2. Else
         1. Set table[subStringStartIndex][subStringEndIndex] = Max (
* table[subStringStartIndex + 1][subStringEndIndex ], table[subStringStartIndex ][subStringEndIndex -1 ])
4. Return table[0][str.length - 1]

Latest Source Code:
Github: LongestPalindromicSubsequence.java

Output:

String: BBABCBCAB
Longest Palindromic Subsequence Length: (Recursive) 7
1 2 2 3 3 5 5 5 7 
0 1 1 3 3 3 3 5 7 
0 0 1 1 1 3 3 5 5 
0 0 0 1 1 3 3 3 5 
0 0 0 0 1 1 3 3 3 
0 0 0 0 0 1 1 1 3 
0 0 0 0 0 0 1 1 1 
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 0 1 
Longest Palindromic Subsequence Length: (By DP) 7

Video