String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding


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.




Solution of Longest Palindromic Subsequence


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<


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
  3. For i=2:n //i is substring length
        For j=0:n-i
            IF(i==2 && s[start]==s[end]) //two letter palindromes
            ELSE IF(s[start]==s[end])
                L[start][end]=2+L[start+1][end-1]; //extend length
                //choose max between two possible substring output
        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.

    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

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

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

    Same for j=2
    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
                //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;


Enter input string
Longest palindromic sub-sequence is: 8

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.