Ways To Find Longest Palindromic Subsequence (+Code Examples)

0 min read

A Longest Palindromic Subsequence (LPS) is the longest sequence of characters in a given string that reads the same forward and backward, but the characters do not need to be contiguous. Unlike the Longest Palindromic Substring, which requires consecutive characters, the LPS problem focuses on identifying the longest possible subsequence that maintains palindromic properties.

In this article, we will explore different approaches to finding the longest palindromic subsequence, including recursive methods, dynamic programming solutions, and space-optimized techniques. We will also analyze their time complexities and provide code examples to illustrate each approach.

What Is The Longest Palindromic Subsequence?

A Longest Palindromic Subsequence (LPS) is the longest sequence of characters in a string that appears in the same order when read forward and backward. However, unlike a palindrome that requires consecutive characters, a subsequence allows skipping some characters as long as the remaining ones maintain the palindromic order.

Example:

Let's take the word "character":

• The longest palindromic subsequence here is "carac" (if we remove some letters while keeping the order).
• Notice that this is different from a palindromic substring, where characters must be consecutive.

Real-Life Analogy

Think of a family heirloom that is passed down through generations. Even if some family traditions change over time, the core values and customs stay intact, maintaining a connection between the past and present.

Similarly, in a string, some characters may be removed, but the order of the remaining ones stays the same, forming a longest palindromic subsequence!

Problem Statement: Longest Palindromic Subsequence (LPS)

Given a string S of length n, the Longest Palindromic Subsequence (LPS) problem requires us to find the longest subsequence of S that reads the same forward and backward. Unlike substrings, subsequences are formed by deleting some or no characters without changing the relative order of the remaining characters.

Mathematical Definition:

For a given string S, find the longest subsequence P such that:

P[i] = P[j] 
for all valid indices i,j where i corresponds to j in reverse order.

The goal is to determine the length of the longest palindromic subsequence in S.

Example 1:

• Input: "character"
• Possible Palindromic Subsequences: "cac", "carac", "cec", etc.
• Longest Palindromic Subsequence: "carac"
• Output: 5

Example 2:

• Input: "bbabcbcab"
• Longest Palindromic Subsequence: "babcbab"
• Output: 7

Example 3:

• Input: "abcdef"
• Longest Palindromic Subsequence: Any single character (e.g., "a", "b", etc.)
• Output: 1

This problem is often solved using recursion, dynamic programming, and optimization techniques to handle large inputs efficiently.

Approaches to Solve Longest Palindromic Subsequence (LPS)

The Longest Palindromic Subsequence (LPS) problem in data structures can be solved using different techniques, each with varying time and space complexity. Below are the key approaches:

1. Naive Recursion
2. Dynamic Programming
3. LCS Approach

Let’s now discuss each of these approaches in detail with code examples.

Naive Recursive Approach

The naive recursive approach explores all possible subsequences and checks if they are palindromic. It is based on a simple idea:

1. If the string has only one character, the longest palindromic subsequence (LPS) is just 1 (a single letter is always a palindrome).
2. If the first and last characters match, they must be part of the LPS. We count them and check the middle part of the string.
3. If the first and last characters don’t match, we have two choices:
• Ignore the first character and solve for the remaining substring.
• Ignore the last character and solve for the remaining substring.
• Take the maximum of both choices.

This method explores all possible subsequences to find the longest palindromic one.

Recursive Formula

• If i == j: LPS(i, j) = 1 (A single character is always a palindrome).
• If S[i] == S[j]: LPS(i, j) = 2 + LPS(i+1, j-1) (If first and last characters match, add 2 and check the middle).
• If S[i] != S[j]: LPS(i, j) = max(LPS(i+1, j), LPS(i, j-1)) (If they don’t match, take the max of ignoring one character).

Time & Space Complexity

• Time Complexity: O(2^n) → Exponential (because we check many overlapping subproblems).
• Space Complexity: O(n) → Recursive stack space (due to function calls).

Code Example:

            #include
using namespace std;

int LPS(string s,int i,int j){
    // Base case: single character is a palindrome of length 1
    if(i==j) return 1;

    // If first and last characters match
    if(s[i]==s[j]&&i+1==j) return 2; // Two matching characters

    if(s[i]==s[j]) 
        return 2+LPS(s,i+1,j-1);

    // If characters don’t match, try both possibilities
    return max(LPS(s,i+1,j),LPS(s,i,j-1));
}

int main(){
    string s="BBABCBCAB";
    int n=s.length();
    cout<<"Length of LPS: "<<LPS(s,0,n-1)<<endl;
    return 0;
}

          

I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgTFBTKHN0cmluZyBzLGludCBpLGludCBqKXsKICAgIC8vIEJhc2UgY2FzZTogc2luZ2xlIGNoYXJhY3RlciBpcyBhIHBhbGluZHJvbWUgb2YgbGVuZ3RoIDEKICAgIGlmKGk9PWopIHJldHVybiAxOwoKICAgIC8vIElmIGZpcnN0IGFuZCBsYXN0IGNoYXJhY3RlcnMgbWF0Y2gKICAgIGlmKHNbaV09PXNbal0mJmkrMT09aikgcmV0dXJuIDI7IC8vIFR3byBtYXRjaGluZyBjaGFyYWN0ZXJzCgogICAgaWYoc1tpXT09c1tqXSkgCiAgICAgICAgcmV0dXJuIDIrTFBTKHMsaSsxLGotMSk7CgogICAgLy8gSWYgY2hhcmFjdGVycyBkb27igJl0IG1hdGNoLCB0cnkgYm90aCBwb3NzaWJpbGl0aWVzCiAgICByZXR1cm4gbWF4KExQUyhzLGkrMSxqKSxMUFMocyxpLGotMSkpOwp9CgppbnQgbWFpbigpewogICAgc3RyaW5nIHM9IkJCQUJDQkNBQiI7CiAgICBpbnQgbj1zLmxlbmd0aCgpOwogICAgY291dDw8Ikxlbmd0aCBvZiBMUFM6ICI8PExQUyhzLDAsbi0xKTw8ZW5kbDsKICAgIHJldHVybiAwOwp9Cg==

Output: 

Length of LPS: 7

Explanation:

In the above C++ code example-

1. We start by including the <iostream> library to handle input and output operations and use using namespace std; to avoid writing std:: repeatedly.
2. The LPS function is a recursive function that calculates the Longest Palindromic Subsequence (LPS) of a given string by considering different character combinations.
3. If the start and end indices (i and j) are the same, it means we are looking at a single character, which is always a palindrome of length 1.
4. If the first and last characters match and are adjacent (i + 1 == j), we have a two-character palindrome, so we return 2.
5. If the first and last characters match but are not adjacent, we add 2 to the LPS of the substring between them (LPS(s, i + 1, j - 1)) because these two characters contribute to the palindrome length.
6. If the characters don’t match, we explore two possibilities:
• Ignoring the first character (LPS(s, i + 1, j))
• Ignoring the last character (LPS(s, i, j - 1))
• We take the maximum of these two values since we want the longest subsequence.
7. The main() function initializes the string "BBABCBCAB" and calculates its length.
8. We call LPS(s, 0, n - 1), which processes the entire string recursively and returns the length of the longest palindromic subsequence.
9. The result is printed using cout function, displaying "Length of LPS: 7", since the longest palindromic subsequence in "BBABCBCAB" is "BABCBAB".

Dynamic Programming Approach

The recursive approach for finding LPS is inefficient because it recomputes the same subproblems multiple times. The Dynamic Programming (DP) approach solves this by storing intermediate results in a DP table to avoid redundant computations.

Here’s the step-by-step approach:

Define a DP table (dp[i][j])

• dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j].

Base Case:

• If there’s only one character, it’s a palindrome of length 1: dp[i][i] = 1

Recursive Relation:

• If first and last characters match (s[i] == s[j]): dp[i][j] = 2 + dp[i+1][j-1]  (We add 2 to the length of the LPS in the remaining substring).
  
  
• If first and last characters don’t match (s[i] != s[j]):  dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (We take the maximum LPS by either ignoring the first or last character).

Final Answer:

• The answer for the whole string is stored in dp[0][n-1] (full range).

Time & Space Complexity

• Time Complexity: O(n^2) →Since we fill an n × n table.
• Space Complexity: O(n^2) → Because of the dp table.

Code Example:

            #include
#include
using namespace std;

int LPS(string s){
    int n=s.length();
    vector<vector> dp(n,vector(n,0));

    // Base case: Single-character palindromes
    for(int i=0;i<n;i++)
        dp[i][i]=1;

    // Fill the table for substrings of length 2 to n
    for(int len=2;len<=n;len++){
        for(int i=0;i<n-len+1;i++){
            int j=i+len-1;
            if(s[i]==s[j])
                dp[i][j]=2+dp[i+1][j-1]; // Match case
            else
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]); // No match case
        }
    }
    return dp[0][n-1]; // The longest palindromic subsequence for full string
}

int main(){
    string s="BBABCBCAB";
    cout<<"Length of LPS: "<<LPS(s)<<endl;
    return 0;
}

          

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBMUFMoc3RyaW5nIHMpewogICAgaW50IG49cy5sZW5ndGgoKTsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZHAobix2ZWN0b3I8aW50PihuLDApKTsKCiAgICAvLyBCYXNlIGNhc2U6IFNpbmdsZS1jaGFyYWN0ZXIgcGFsaW5kcm9tZXMKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgZHBbaV1baV09MTsKCiAgICAvLyBGaWxsIHRoZSB0YWJsZSBmb3Igc3Vic3RyaW5ncyBvZiBsZW5ndGggMiB0byBuCiAgICBmb3IoaW50IGxlbj0yO2xlbjw9bjtsZW4rKyl7CiAgICAgICAgZm9yKGludCBpPTA7aTxuLWxlbisxO2krKyl7CiAgICAgICAgICAgIGludCBqPWkrbGVuLTE7CiAgICAgICAgICAgIGlmKHNbaV09PXNbal0pCiAgICAgICAgICAgICAgICBkcFtpXVtqXT0yK2RwW2krMV1bai0xXTsgLy8gTWF0Y2ggY2FzZQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBkcFtpXVtqXT1tYXgoZHBbaSsxXVtqXSxkcFtpXVtqLTFdKTsgLy8gTm8gbWF0Y2ggY2FzZQogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBkcFswXVtuLTFdOyAvLyBUaGUgbG9uZ2VzdCBwYWxpbmRyb21pYyBzdWJzZXF1ZW5jZSBmb3IgZnVsbCBzdHJpbmcKfQoKaW50IG1haW4oKXsKICAgIHN0cmluZyBzPSJCQkFCQ0JDQUIiOwogICAgY291dDw8Ikxlbmd0aCBvZiBMUFM6ICI8PExQUyhzKTw8ZW5kbDsKICAgIHJldHVybiAwOwp9Cg==

Output: 

Length of LPS: 7

Explanation:

In the above code example-

1. We include <iostream> for input and output operations and <vector> to use a 2D dynamic programming (DP) table.
2. The LPS function takes a string as input and computes the Longest Palindromic Subsequence (LPS) using dynamic programming instead of recursion.
3. We initialize a 2D DP table (dp) of size n × n, where dp[i][j] stores the LPS length for the substring s[i...j].
4. Base case: Every single character is a palindrome of length 1, so we fill the diagonal dp[i][i] = 1.
5. We iterate over possible substring lengths (len), starting from 2 up to n.
6. For each substring of length len, we determine its starting (i) and ending (j) indices and check:
• If s[i] == s[j], these two characters contribute to the LPS, so we add 2 to dp[i+1][j-1] (the LPS of the inner substring).
• If s[i] != s[j], we take the maximum LPS from either ignoring the first character (dp[i+1][j]) or ignoring the last character (dp[i][j-1]).
7. Once the DP table is filled, dp[0][n-1] gives the length of the longest palindromic subsequence for the entire string.
8. In main, we test the function on "BBABCBCAB" and print the result. The output is "Length of LPS: 7", since "BABCBAB" is the longest palindromic subsequence.

Using Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) is a classic problem that finds the longest subsequence common to two given sequences. We can leverage LCS to find the Longest Palindromic Subsequence (LPS) by using the following idea:

Key Idea: Relationship Between LPS And LCS

A palindrome reads the same forward and backward. So, if we reverse the given string, the LCS of the original string and its reversed version gives the LPS.

Steps To Solve LPS Using LCS:

1. Reverse the original string:

• Given s = "BBABCBCAB", the reversed version is rev_s = "BACBCBAB"

2. Find the LCS of s and rev_s

• The LCS of "BBABCBCAB" and "BACBCBAB" is "BABCBAB", which is the LPS of s.

3. LCS is solved using Dynamic Programming:

• We construct an LCS table (dp[i][j]) where: dp[i][j] stores the LCS length for substrings s[0…i-1] and rev_s[0…j-1].

4. Final Answer:

• The value at dp[n][n] (where n is the string length) gives the length of LPS.

Time & Space Complexity

• Time Complexity: O(n^2) → Standard LCS algorithm complexity.
• Space Complexity: O(n^2) → Due to the dp table.

Code Example:

            #include
#include
using namespace std;

// Function to compute LCS of two strings
int LCS(string s1,string s2){
    int n=s1.length();
    vector<vector> dp(n+1,vector(n+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s1[i-1]==s2[j-1])
                dp[i][j]=1+dp[i-1][j-1]; // Matching case
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]); // No match case
        }
    }
    return dp[n][n]; // LPS length
}

int LPS(string s){
    string rev_s=string(s.rbegin(),s.rend()); // Reverse the string
    return LCS(s,rev_s); // Find LCS of original and reversed string
}

int main(){
    string s="BBABCBCAB";
    cout<<"Length of LPS: "<<LPS(s)<<endl;
    return 0;
}

          

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEZ1bmN0aW9uIHRvIGNvbXB1dGUgTENTIG9mIHR3byBzdHJpbmdzCmludCBMQ1Moc3RyaW5nIHMxLHN0cmluZyBzMil7CiAgICBpbnQgbj1zMS5sZW5ndGgoKTsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZHAobisxLHZlY3RvcjxpbnQ+KG4rMSwwKSk7CiAgICBmb3IoaW50IGk9MTtpPD1uO2krKyl7CiAgICAgICAgZm9yKGludCBqPTE7ajw9bjtqKyspewogICAgICAgICAgICBpZihzMVtpLTFdPT1zMltqLTFdKQogICAgICAgICAgICAgICAgZHBbaV1bal09MStkcFtpLTFdW2otMV07IC8vIE1hdGNoaW5nIGNhc2UKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgZHBbaV1bal09bWF4KGRwW2ktMV1bal0sZHBbaV1bai0xXSk7IC8vIE5vIG1hdGNoIGNhc2UKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gZHBbbl1bbl07IC8vIExQUyBsZW5ndGgKfQoKaW50IExQUyhzdHJpbmcgcyl7CiAgICBzdHJpbmcgcmV2X3M9c3RyaW5nKHMucmJlZ2luKCkscy5yZW5kKCkpOyAvLyBSZXZlcnNlIHRoZSBzdHJpbmcKICAgIHJldHVybiBMQ1MocyxyZXZfcyk7IC8vIEZpbmQgTENTIG9mIG9yaWdpbmFsIGFuZCByZXZlcnNlZCBzdHJpbmcKfQoKaW50IG1haW4oKXsKICAgIHN0cmluZyBzPSJCQkFCQ0JDQUIiOwogICAgY291dDw8Ikxlbmd0aCBvZiBMUFM6ICI8PExQUyhzKTw8ZW5kbDsKICAgIHJldHVybiAwOwp9Cg==

Output: 

Length of LPS: 7

Explanation:

In the above code example-

1. We include <iostream> for input and output operations and <vector> to store the dynamic programming (DP) table.
2. The LCS function computes the Longest Common Subsequence (LCS) of two strings using dynamic programming.
3. We initialize a 2D DP table (dp) of size (n+1) × (n+1), where dp[i][j] stores the length of the LCS for the first i characters of s1 and the first j characters of s2.
4. We iterate through both strings:
• If s1[i-1] == s2[j-1], the characters match, so we add 1 to dp[i-1][j-1].
• If the characters don’t match, we take the maximum value from either ignoring a character from s1 (dp[i-1][j]) or s2 (dp[i][j-1]).
5. The final result, stored in dp[n][n], gives the length of the LCS of s1 and s2.
6. The LPS function finds the Longest Palindromic Subsequence (LPS) by computing the LCS of the original string and its reverse.
7. In main, we test the function on "BBABCBCAB" and print the result. The output is "Length of LPS: 7", since the longest palindromic subsequence is "BABCBAB".
8. This LCS-based approach runs in O(n²) time, using O(n²) space, similar to the traditional DP approach for LPS.

Comparative Analysis of Longest Palindromic Subsequence (LPS) Approaches

Here is a comparative analysis of different approaches to finding the Longest Palindromic Subsequence (LPS):

Key Takeaways

• If the string is small, a recursive approach is fine for understanding the problem.
• For larger inputs, DP is the best choice as it reduces redundant calculations.
• LCS-based approach is useful if you’re already familiar with LCS concepts.

Applications of Longest Palindromic Subsequence (LPS)

The Longest Palindromic Subsequence (LPS) has several real-world applications, particularly in fields that involve sequence analysis and pattern recognition. Here are some key areas where LPS is useful:

1. Bioinformatics & DNA Sequence Analysis

• DNA sequences often contain palindromic patterns, which are crucial for genetic mutations, evolution tracking, and protein structure prediction.
• LPS helps in analyzing genome sequences to identify patterns that may have biological significance.

2. Text Processing & Data Compression

• Used in text similarity detection where identifying palindromic structures helps in recognizing patterns in documents.
• Helps in data compression algorithms by eliminating redundant sequences in large texts.

3. Competitive Programming & Algorithm Design

• Frequently appears in coding competitions and interviews, testing knowledge of dynamic programming and recursion.
• Acts as a building block for other string-processing problems like Palindrome Partitioning and Longest Repeated Subsequence.

4. Cryptography & Security

• LPS is used in cryptographic key generation, where palindromic sequences are leveraged to enhance encryption techniques.
• Helps in pattern detection in encrypted messages by analyzing symmetry-based sequences.

5. Audio & Speech Processing

• Used in speech recognition and sound wave analysis where certain phonetic patterns exhibit repetitive structures.
• Helps in analyzing musical compositions to detect symmetry-based patterns in melodies.

Conclusion

The Longest Palindromic Subsequence (LPS) is a fundamental problem in string processing with applications spanning bioinformatics, cryptography, text analysis, and competitive programming. We explored multiple approaches to solving LPS, from the naive recursive method to dynamic programming and LCS-based techniques, each with its advantages and trade-offs.

For practical applications, Dynamic Programming is the most efficient approach due to its quadratic time complexity and ability to handle large inputs effectively. If memory optimization is crucial, space-efficient variations can further reduce the storage overhead.

Understanding LPS not only improves problem-solving skills but also lays the groundwork for tackling more complex sequence analysis problems. Whether you're working with genetic sequences, encrypted data, or pattern recognition tasks, LPS provides valuable insights into identifying symmetry and structure in data.

Frequently Asked Questions

Q1. What is the difference between Longest Palindromic Substring and Longest Palindromic Subsequence?

A Longest Palindromic Substring is a contiguous sequence of characters that forms a palindrome, whereas a Longest Palindromic Subsequence is a subsequence that can be obtained by deleting characters while maintaining their relative order. Example: For "abdbca", the LPS is "bdb" or "aba", but the longest palindromic subsequence is "aba" or "bdb" or "abcba", depending on deletions.

Q2. Why is Dynamic Programming preferred over recursion for solving LPS?

The recursive approach explores all possible subsequences, leading to an exponential time complexity O(2^n), making it inefficient for large inputs. Dynamic Programming (DP) stores intermediate results, avoiding redundant calculations, and runs in O(n^2) time, making it far more efficient.

Q3. How is LPS related to the Longest Common Subsequence (LCS)?

The LCS approach to LPS works by finding the LCS of the given string and its reverse. This works because a palindrome remains the same when reversed, meaning the longest matching sequence between the original and its reverse is the longest palindromic subsequence.

Q4. Can LPS be used in real-world applications?

Yes! LPS has applications in bioinformatics (DNA pattern analysis), data compression, cryptography, and text processing, where identifying palindromic structures helps in pattern recognition and security algorithms.

Q5. Why does the Longest Palindromic Subsequence (LPS) problem require dynamic programming for efficient solving?

The LPS problem involves finding the longest subsequence within a string that reads the same forward and backward. Since subsequences are non-contiguous, there are multiple possible choices at each step, leading to overlapping subproblems and optimal substructure, which makes Dynamic Programming (DP) the ideal approach.

1. Overlapping Subproblems:

The recursive solution repeatedly solves the same subproblems, leading to redundant calculations. For example, in a string "abdbca", the subsequence computations for "bdb" may be computed multiple times when checking different parts of the string. DP stores intermediate results in a table to avoid recomputation.

2. Optimal Substructure:

LPS exhibits optimal substructure, meaning the solution to the whole problem is built from the solutions of smaller subproblems. If s[i] == s[j], then the LPS for s[i:j] depends on s[i+1:j-1], ensuring that solving smaller problems first leads to the solution of the larger problem.

3. Why Not Use Greedy Algorithms?

Greedy algorithms make local choices without considering future consequences. However, for LPS, a local decision (such as always choosing the longest matching pair of characters) does not always lead to the global optimum. This is why DP, which considers all possibilities systematically, is necessary.

4. Practical Applications of DP in LPS:

• Bioinformatics: Identifying symmetrical DNA sequences.
• Text Processing: Detecting palindromic patterns in large texts.
• Data Compression: Finding recurring sequences for compression algorithms.

Q6. What is the best approach for solving LPS in large datasets?

For large strings, Dynamic Programming is the best approach, as it provides a balance between time efficiency (O(n^2)) and manageable space complexity. If memory is a constraint, a space-optimized DP approach using only two rows instead of a full DP table can be used.

Suggested Reads: 

1. What Is Selection Sort Algorithm? Explained With Code Examples
2. Learn All About Bubble Sort Algorithm (With Code Examples)
3. Merge Sort Algorithm | Working, Applications & More (+Examples)
4. Quick Sort Algorithm | Working, Applications & More (+Examples)
5. Heap Sort Algorithm - Working And Applications (+ Code Examples)