Home » Interview coding problems/challenges

Find out the length of the longest palindromic subsequence from a string

Here, we are going to learn how to find out the length of longest palindromic subsequences of a string using dynamic programming? Submitted by Souvik Saha, on March 31, 2020

Problem statement

Given a string you have to find out the length of the longest palindromic subsequence from the given string.

    Input:
    T Test case
    T no of input string will be given to you.

    E.g.
    3
    
    bghaufaght
    souabbuos
    sahajkhahas
    
    Constrain 
    1≤ length (string) ≤100 
    
    Output:
    Print the length of the longest palindromic sub sequences from that string

Example

    T=3

    Input:
    bghaufahgt 
    
    Output:
    7 (ghafahg)
    
    Input:
    souabbuos
    
    Output:
    8 (soubbuos)
    
    Input:
    sahajkhahas
    
    Output:
    9 (sahajahas)

Explanation with example

Let there is a string str.

Now possible arrangements are:

1. Single middle characters like aba
2. Paired middle characters like bb

Let, f(a,b) = length of palindromic substring from index a to index b.

Considering the above three facts:

1. If there is only one character then f(a,a) = 1
2. If there are two characters a and a+1 both are same then f(a,a+1) = 2 if both are not same then f(a,a+1) = 1.
3. If there is a substring starting from index a to index b then,
   1. If str[a] and str[b] both are same then f(a,b) = f(a+1,b-1) + 2
   2. If str[a] and str[b] both are not same then f(a,b)= max{ f(a+1,b) , f(a,b-1) }

For, str = bghaufahgt

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int length_of_palindrom(string str)
{
    int len = str.length();
    int arr[len][len];
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i < len; i++) {
        arr[i][i] = 1;
    }
    //for the paired middle character
    for (int i = 0; i < len - 1; i++) {
        if (str[i] == str[i + 1])
            arr[i][i + 1] = 2;
        else
            arr[i][i + 1] = 1;
    }
    //length wise traversal
    for (int l = 3; l <= len; l++) {
        for (int i = 0; i <= len - l; i++) {
            int j = i + l - 1;
            if (str[i] == str[j])
                arr[i][j] = arr[i + 1][j - 1] + 2;
            else
                arr[i][j] = max(arr[i + 1][j], arr[i][j - 1]);
        }
    }
    return arr[0][len - 1];
}

int main()
{
    int t;
    cout << "Test Case : ";
    cin >> t;
    while (t--) {
        cout << "Enter the string : ";
        string str;
        cin >> str;
        cout << "Length of the palindrome: " << length_of_palindrom(str) << endl;
    }
}

Output

Test Case : 3
Enter the string : bghaufahgt
Length of the palindrome: 7
Enter the string : souabbuos
Length of the palindrome: 8
Enter the string : sahajkhahas
Length of the palindrome: 9