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

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

2022-04-30

360

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

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)

C++ programming, Interview questions, C++ programming Interview-questions,

All Answers

mahmoud2506

2022-04-30

need an explanation for this answer? contact us directly to get an explanation for this answer

Let there is a string str.

Now possible arrangements are:

Single middle characters like aba
Paired middle characters like bb

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

Considering the above three facts:

If there is only one character then f(a,a) = 1
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.
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

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

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)