Q:

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

0

Find out the longest palindromic subsequence from a string

Given a string you have to find out 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
    
    bghaufahgt
    souabbuos
    sahajkhahas
    
    Constrain 
    1≤ length (string) ≤100
    
    Output:
    Print the longest palindromic subsequence from that string

Example

    T=3

    Input:
    bghaufahgt
    
    Output:
    ghafahg
    
    Input:
    souabbuos
    
    Output:
    soubbuos
    
    Input:
    sahajkhahas
    
    Output:
    sahajahas

 

All Answers

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

To find out the characters in the palindrome we will follow this approach:

  1. The max length will be the top right block.
  2. Every time we will check the left and bottom adjacent blocks.
    1. If both the blocks contain the same value then we will go for any of them.
    2. If any block contains a value such that the difference between the current value and the value at the block is 2 then we will go for that block and make a note of that character present in the string whose index is the same as the column number.
    3. When we will get the value equals to 1 then stop the traversal.
Find out the longest palindromic subsequence from a string

 

C++ Implementation:

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

int arr[101][101];

void print_palindrome(string str)
{
    int len = str.length();
    int i = 0;
    int j = len - 1;
    int num = arr[i][j];
    vector<char> v;
    int flag = 0;
    while (i < len && j >= 0) {
        if (num == 2) {
            flag = 1;
            break;
        }
        if (num == 1)
            break;
        //if the left block has the value by which
        //the difference will be 2
        if (arr[i][j - 1] + 2 == num) {
            v.push_back(str[j]);
            j--;
            num = arr[i][j];
            if (num == 1 || num == 2) {
                v.push_back(str[j]);
            }
        }
        //if the bottam block has the value by
        //which the difference will be 2
        if (arr[i + 1][j] + 2 == num) {
            v.push_back(str[i]);
            i++;
            num = arr[i][j];
            if (num == 1 || num == 2) {
                v.push_back(str[i]);
            }
        }
        if (arr[i][j - 1] == num) {
            j--;
        }
        else {
            i++;
        }
    }
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
    }
    //cout<<endl;
    for (int i = v.size() - 1; i >= 0; i--) {
        if (flag && i == v.size() - 1) {
            cout << v[i];
        }
        else if (i != v.size() - 1) {
            cout << v[i];
        }
    }
    cout << endl;
}

void length_of_palindrom(string str)
{
    int len = str.length();
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i < len; i++) {
        arr[i][i] = 1;
    }
    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;
    }
    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]);
        }
    }
    cout << "Palindrome : ";
    print_palindrome(str);
    cout << endl;
    return;
}

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

Output

 

Test Case : 3
Enter the string : bghaufahgt
Palindrome : ghafahg

Enter the string : souabbuos
Palindrome : soubbuos

Enter the string : sahajkhahas
Palindrome :  sahajahas

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

total answers (1)

interview C++ coding problems/challenges | dynamic programming

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
Given a string you have to find out the length of ... >>
<< Given an array you have to print the longest biton...