# Longest Palindromic Subsequence

### Longest Palindromic Subsequence

##### 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
```
Author: