Longest Palindromic Subsequence

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

Author: Hrishikesh Mishra

  • Wang Shuhao

    but what if you are asked to get the longest palindrome sub string?