Q:

# Longest Palindromic Subsequence

Given a string find the length of longest palindromic subsequence.

Example:

```    Input:
abaccaabbaa
Output:
6

Input:
aaa
Output:
3```

Let,

L(i,j)=length of subsequence from index i to j having length j-i+1
L(i,i)=1 ... base case

It's obvious because each single letter is itself a palindrome and thus every string has palindrome of length 1.

L(i,i) = substring starting from i ending at i, i.e, a single letter<

Now,

L(i,j)=2+L(i+1,j-1) if string[i]=string[j]
L(i,j)=max⁡(L(i+1,j),L(i,j-1)) if string[i]≠string[j]

This is quite obvious : If string[i]=string[j] then it just extends whatever is value for L(i+1,j-1). Else we take the longest possible value so far.

We can actually convert these recursive definitions to our DP matrix.

1. Let the DP matrix to be L[n][n] where n is string length. Reasons behind the dimensions are maximum possible start and end index value can be n-1
Initialize DP matrix with 0.
2. For base case,
```For i=0:n-1
L[i][i]=1
```
3. ```For i=2:n //i is substring length
For j=0:n-i
start=j;
end=j+i-1;
IF(i==2 && s[start]==s[end]) //two letter palindromes
L[start][end]=2;
ELSE IF(s[start]==s[end])
L[start][end]=2+L[start+1][end-1]; //extend length
ELSE
//choose max between two possible substring output
L[start][end]=max(L[start+1][end],L[start][end-1]);
END For
END For
```
4. L[n-1] is our final result (0 starting index, n-1 end index)

Example with explanation:

```    Let's see the example1.
abaccaabbaa

Longest palindromic sub sequence can be:
abaccaba (subsequence is not similar to substring)
Thus longest one has length 8
Now check how actually program worked
For 1 length
L[i][i] =1
So the left to right diagonal actually becomes 1
Now for each possible length of 2 to n
We start from index 0 and keep incrementing
We can actually review first few iterations
So for i=2
-------------------------------------------------

J=0
Start =0
End =1 //(i+j-1)
I==2 but s≠s
L=0 //no updating
-------------------------------------------------

J=1
Start =1
End =2//(i+j-1)
I==2 but s≠s
L=0 //no updating
-------------------------------------------------

Same for j=2
J=3
Start =3
End =4 //(i+j-1)
I==2 and s=s
L=2 //updating here
```

Similarly we can carry on iterations for all length and ultimately L[n-1] gives the final result

C++ implementation:

``````#include <bits/stdc++.h>
using namespace std;

void print(vector<int> a,int n){
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

int max(int a,int b){
return (a>b)?a:b;
}

int LPS(string s){
int n=s.length();
int start,end;

int L[n][n];
memset(L,0,sizeof(L)); //initialize to 0

for(int i=0;i<n;i++) //base case of single letter string
L[i][i]=1;

for(int i=2;i<=n;i++){ //i is length of string
for(int j=0;j<n-i+1;j++){ //j=starting index
start=j;
end=j+i-1;
if(i==2 && s[start]==s[end]) //two length palindrome
L[start][end]=2;
else if(s[start]==s[end]) //if s[start]=s[end]
L[start][end]=2+L[start+1][end-1]; //extend
else
//take max of possible two substring output
L[start][end]=max(L[start+1][end],L[start][end-1]);
}
}
return L[n-1]; //final result
}

int main()
{
int t,n,item;
string s;

cout<<"Enter input string\n";
cin>>s;

cout<<"Longest palindromic sub-sequence is: ";
cout<<LPS(s)<<endl;

return 0;
}``````

Output

```Enter input string
abaccaabbaa
Longest palindromic sub-sequence is: 8```