Understanding Longest Palindrome Subsequence | DSA in C++ - Software Development PDF Download

Introduction

In this article, we will explore the concept of finding the Longest Palindrome Subsequence (LPS) in a given string using the C++ programming language. We will start by understanding what a palindrome is and then delve into the concept of a subsequence. We will provide multiple examples along with simple code snippets, explanations, and visual aids to make it easier for beginners to grasp the topic.

What is a Palindrome?

A palindrome is a sequence of characters that reads the same forward and backward. For example, "radar" and "level" are palindromic strings because they can be read the same way from left to right or right to left.

What is a Subsequence?

A subsequence of a string is a new string that can be derived from the original string by deleting some or no characters without changing the order of the remaining characters. For instance, for the string "OpenAI," some of its subsequences are "OAI," "penA," and "OpenAI" itself.

Longest Palindrome Subsequence (LPS) Explained

The Longest Palindrome Subsequence (LPS) refers to the longest subsequence of a given string that is also a palindrome. It means that the subsequence needs to maintain the order of characters as in the original string while ignoring characters that are not part of the palindrome.

Finding the LPS in C++

Dynamic Programming Approach

To find the LPS of a given string, we can use a dynamic programming approach. We can create a table to store the lengths of the longest palindromic subsequences for different subproblems.

Code Explanation and Example

#include <iostream>

#include <cstring>

using namespace std;

int longestPalindromeSubseq(string str) {

    int n = str.length();

    int dp[n][n];

    // Each character is a palindrome of length 1

    for (int i = 0; i < n; i++)

        dp[i][i] = 1;

    for (int len = 2; len <= n; len++) {

        for (int i = 0; i <= n - len; i++) {

            int j = i + len - 1;

            if (str[i] == str[j] && len == 2)

                dp[i][j] = 2;

            else if (str[i] == str[j])

                dp[i][j] = dp[i + 1][j - 1] + 2;

            else

                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);

        }

    }

    return dp[0][n - 1];

}

int main() {

    string str = "level";

    int lpsLength = longestPalindromeSubseq(str);

    cout << "Length of the Longest Palindrome Subsequence: " << lpsLength << endl;

    return 0;

}

Explanation:

• We define a 2D array 'dp[][]' to store the lengths of palindromic subsequences.
• We initialize the diagonal elements with 1 since each character is a palindrome of length 1.
• We iterate over the remaining subproblems, starting from substrings of length 2 up to the entire length of the string.
• If the characters at the current indices are the same, we add 2 to the length of the palindrome by considering the remaining string inside the current substring.
• If the characters are different, we update the table by taking the maximum of the lengths of the palindromic subsequences obtained by either excluding the first character or the last character of the current substring.
• Finally, the length of the LPS is stored in 'dp[0][n-1]', where 'n' is the length of the input string.

Output:

Length of the Longest Palindrome Subsequence: 3

Explanation of Output:

For the string "level," the longest palindromic subsequence is "eve" or "ele," both of which have a length of 3.

Sample Problems and Solutions

Problem 1: Given the string "banana," find the length of the longest palindromic subsequence.

The longest palindromic subsequence for "banana" is "anana," which has a length of 5.

Problem 2: Given the string "abracadabra," find the length of the longest palindromic subsequence.

The longest palindromic subsequence for "abracadabra" is "araara," which has a length of 6.

Conclusion

In this article, we learned about palindromes, subsequences, and the concept of the Longest Palindrome Subsequence (LPS). We explored a dynamic programming approach to find the LPS in a given string using C++. By understanding the code and examples provided, beginners can now solve similar problems involving palindromic subsequences.