सबसे लंबा पैलिंड्रोमिक सबसीक्वेंस

सबसे लंबा पैलिंड्रोमिक सबसीक्वेंस एक दिए गए अनुक्रम का सबसीक्वेंस है, और वह सबसीक्वेंस एक पैलिंड्रोम है।

इस समस्या में, एक कैरेक्टर अनुक्रम दिया गया है, हमें पैलिंड्रोमिक सबसीक्वेंस की सबसे लंबी लंबाई ढूंढनी है।

इस समस्या को हल करने के लिए, हम रिकर्सिव फॉर्मूला का उपयोग कर सकते हैं:

यदि L(0, n-1) सबसे लंबे पैलिंड्रोमिक सबसीक्वेंस की लंबाई स्टोर करता है, तो
L(0, n-1) := L(1, n-2) + 2 (जब 0वां और (n-1)वां कैरेक्टर समान हों)।

इनपुट और आउटपुट

इनपुट: अलग-अलग अक्षरों या प्रतीकों वाली एक स्ट्रिंग। मान लें इनपुट "ABCDEEAB" है
आउटपुट: सबसे बड़े पैलिंड्रोमिक सबसीक्वेंस की सबसे लंबी लंबाई। यहां यह 4 है।
ABCDEEAB। तो पैलिंड्रोम है AEEA।

एल्गोरिदम

palSubSeqLen(str)

इनपुट: दी गई स्ट्रिंग
आउटपुट: सबसे लंबे पैलिंड्रोमिक सबसीक्वेंस की लंबाई

शुरुआत
    n = स्ट्रिंग की लंबाई
    lenTable नामक n x n आकार की टेबल बनाएं और 1s से भरें
    col := 2 से n तक, करें
        i := 0 से n - col तक, करें
            j := i + col - 1
            यदि str[i] = str[j] और col = 2, तो
                lenTable[i, j] := 2
            अन्यथा यदि str[i] = str[j], तो
                lenTable[i, j] := lenTable[i+1, j-1] + 2
            अन्यथा
                lenTable[i, j] := lenTable[i, j-1] और lenTable[i+1, j] का अधिकतम
        पूर्ण
    पूर्ण
    वापस lenTable[0, n-1]
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int max(int x, int y) {
    return (x > y) ? x : y;
}

int palSubseqLen(string str) {
    int n = str.size();
    int lenTable[n][n];
    
    for (int i = 0; i < n; i++)
        lenTable[i][i] = 1;
    
    for (int col = 2; col <= n; col++) {
        for (int i = 0; i < n-col+1; i++) {
            int j = i + col - 1;
            if (str[i] == str[j] && col == 2)
                lenTable[i][j] = 2;
            else if (str[i] == str[j])
                lenTable[i][j] = lenTable[i+1][j-1] + 2;
            else
                lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
        }
    }
    return lenTable[0][n-1];
}

int main() {
    string sequence = "ABCDEEAB";
    int n = sequence.size();
    cout << "The length of the longest palindrome subsequence is: " << palSubseqLen(sequence);
}

आउटपुट

The length of the longest palindrome subsequence is: 4