Home » Interview coding problems/challenges

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

Problem statement:

Given a string find the length of longest palindromic subsequence.

Example:

    Input:
    abaccaabbaa
    Output:
    6

    Input:
    aaa
    Output:
    3

Solution:

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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL







Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.