A palindromic subsequence is a subsequence of a string that reads the same backward as forward. The Longest Palindromic Subsequence Problem aims to find the longest subsequence of a given string that is a palindrome.

Program Structure

• Input: A string for which the longest palindromic subsequence needs to be found.
• Output: The length of the longest palindromic subsequence.
• Dynamic Programming: The program uses a 2D array to store lengths of palindromic subsequences for various substrings.

C++ Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Function to find the length of the longest palindromic subsequence
int longestPalindromicSubsequence(const string &s) {
    int n = s.length();
    
    // Create a 2D array to store lengths of palindromic subsequences
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // Every single character is a palindrome of length 1
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // Fill the dp array
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i < n - length + 1; i++) {
            int j = i + length - 1;
            if (s[i] == s[j] && length == 2) {
                dp[i][j] = 2; // Two same characters
            } else if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2; // Characters match
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]); // Characters do not match
            }
        }
    }

    // The length of the longest palindromic subsequence is in dp[0][n-1]
    return dp[0][n - 1];
}

int main() {
    string s;

    // Input the string
    cout << "Enter the string: ";
    cin >> s;

    // Find the longest palindromic subsequence
    int length = longestPalindromicSubsequence(s);

    // Output the result
    cout << "Length of the Longest Palindromic Subsequence: " << length << endl;

    return 0;
}

Explanation of the Code

The code consists of the following main components:

• Input Handling: The program prompts the user to enter a string.
• Palindrome Length Calculation: The longestPalindromicSubsequence function utilizes dynamic programming to fill a 2D vector dp. Here, dp[i][j] stores the length of the longest palindromic subsequence in the substring s[i..j].
• Initialization: Each single character is initialized as a palindrome of length 1.
• Dynamic Programming Logic: The function iteratively checks for matches between characters and updates the dp table based on whether the characters are equal or not.
• Output: The program displays the length of the longest palindromic subsequence found in the string.

Conclusion

This program effectively calculates the length of the longest palindromic subsequence using dynamic programming techniques, making it a valuable tool for solving string manipulation problems.