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 [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

---