### Longest Palindromic Subsequence

##### Given a string, find a longest palindromic subsequence 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:

- Create dp table of
`(str.length) X (str.length)`

- Update table for substring length 1
- Iterate substring length 2 to str.length
- Iterate all subStrings of length i
- If first and last character of substring is equal then
- Set
`table[subStringStartIndex][subStringEndIndex] = 2 + table[subStringStartIndex + 1][subStringEndIndex -1]`

- Set
- Else
- Set
`table[subStringStartIndex][subStringEndIndex] = Max (`

* table[subStringStartIndex + 1][subStringEndIndex ], table[subStringStartIndex ][subStringEndIndex -1 ])

- Set

- If first and last character of substring is equal then

- Iterate all subStrings of length i
- 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