# Longest Palindromic Subsequence

In this article, we are going to see how to find longest palindromic subsequence? This is very famous Dynamic programming program featured in many interview rounds.
Submitted by Radib Kar, on April 01, 2019 [Last updated : March 20, 2023]

## Problem Description

Given a string find the length of longest palindromic subsequence.

## Example

```    Input:
abaccaabbaa
Output:
6

Input:
aaa
Output:
3
```

## Solution of Longest Palindromic Subsequence

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[0][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[0]≠s[1]
L[0][1]=0 //no updating
-------------------------------------------------

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

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

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

### C++ implementation of Longest Palindromic Subsequence

```#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[0][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
```