Given a string find the length 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:

#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