Longest Palindromic Subsequence: A Dynamic Programming Approach

Welcome back! In our last lesson, we mastered the technique of reconstructing the Longest Common Subsequence (LCS) by backtracking through a completed DP table. We saw that the table is not just for finding a length, but a roadmap of the optimal choices made.

Today, we'll apply this powerful LCS pattern to solve a new, though related, problem: finding the Longest Palindromic Subsequence (LPS). This lesson will show you a classic and elegant problem-solving technique in dynamic programming: reducing a new problem to one you already know how to solve. We will demonstrate that finding the LPS of a string is equivalent to finding the LCS between the string and its reverse.

1. Defining the Problem: Longest Palindromic Subsequence

First, let's be clear about what we're looking for. A subsequence is formed by deleting zero or more characters from a string while maintaining the relative order of the remaining characters. A palindrome is a sequence that reads the same forwards and backward.

Therefore, the Longest Palindromic Subsequence is the longest possible subsequence of a string that is also a palindrome.

At first glance, this seems like a new DP problem requiring its own recurrence relation. While that's one way to solve it, there's a much more direct and insightful approach that leverages our work from the previous lessons.

2. The Core Insight: Reducing LPS to LCS

The key insight is this:

The length of the longest palindromic subsequence of a string s is identical to the length of the longest common subsequence between s and its reverse, reverse(s).

This is a powerful reduction. It means we don't need to invent a new algorithm; we can simply reuse the LCS algorithm we've already mastered.

But why does this work? Let's build the intuition. A sequence p is a palindrome if p is equal to reverse(p).

Consider a string s and its reverse, s_rev. Any subsequence that is common to both s and s_rev must have a special property. The following video provides an excellent and intuitive explanation for why any common subsequence between a string and its reverse must be a palindrome.

To summarize the argument from the video:

1. Let's say we have a string s. We create s_rev = reverse(s).
2. Now, we find the LCS of s and s_rev. Let's call this LCS result p.
3. By definition, p is a subsequence of s.
4. Also by definition, p is a subsequence of s_rev.
5. If p is a subsequence of s_rev, it means that the characters of p appear in s in reverse order.
6. For p to be a subsequence of both s (forward order) and s_rev (reverse order), p must be equal to its own reverse.
7. Therefore, any common subsequence p must be a palindrome. The Longest Common Subsequence algorithm will naturally find the Longest Palindromic Subsequence.

3. Implementation: A Simple Wrapper

Now that we understand the "why," the "how" becomes incredibly straightforward. We can implement the longestPalindromeSubseq function as a simple wrapper around our existing longestCommonSubsequence function.

This article provides several implementations, but the core idea is the same across all of them.

Let's write out the complete code. We'll include the tabulation-based LCS length function from our previous studies for context.

def longest_common_subsequence_length(text1: str, text2: str) -> int:
    """Calculates the length of the LCS of two strings using bottom-up DP."""
    m, n = len(text1), len(text2)
    



    # dp[i][j] will be the length of LCS of text1[0...i-1] and text2[0...j-1]
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                
    return dp[m][n]

def longest_palindrome_subseq_length(s: str) -> int:
    """
    Calculates the length of the LPS by reducing it to an LCS problem.
    """
    s_rev = s[::-1]  # Python's slice notation to reverse a string
    return longest_common_subsequence_length(s, s_rev)




# Let's test with the example from the image
s1 = "BANANA"
print(f"The length of the LPS for '{s1}' is: {longest_palindrome_subseq_length(s1)}") # Expected: 5 ("ANANA")

s2 = "bbbab"
print(f"The length of the LPS for '{s2}' is: {longest_palindrome_subseq_length(s2)}") # Expected: 4 ("bbbb")

s3 = "cbbd"
print(f"The length of the LPS for '{s3}' is: {longest_palindrome_subseq_length(s3)}") # Expected: 2 ("bb")

The time complexity is determined entirely by the LCS algorithm, which is $O(N^2)$ where $N$ is the length of the string s. The space complexity for this version is also $O(N^2)$ due to the DP table.

4. Reconstructing the Palindrome and Space Optimization

Just like with the standard LCS problem, we can do more than just find the length.

Reconstructing the LPS String:
If you need to find the actual palindromic subsequence string, you can reuse the reconstruction logic from our previous lesson. You would simply call your get_lcs_string function with the original string and its reverse: get_lcs_string(s, s_rev). The full DP table is required for the backtracking path.

Space Optimization:
In an interview, if you are only asked for the length of the LPS, you can use the space-optimized version of the LCS algorithm. This reduces the space complexity from $O(N^2)$ to $O(N)$ by only keeping track of the previous and current rows of the DP table.

The Code and Debug article you read earlier has a section on this.

This trade-off is crucial: the $O(N)$ space optimization allows you to find the length efficiently but sacrifices the ability to reconstruct the subsequence string, as the full backtracking path information is lost.

Conclusion

In this lesson, we saw how a new problem, Longest Palindromic Subsequence, can be elegantly solved by transforming it into a familiar one, Longest Common Subsequence. This is a powerful problem-solving pattern that frequently appears in algorithm design.

Key Takeaways:

• LPS Definition: The Longest Palindromic Subsequence is the longest subsequence of a string that reads the same forwards and backward.
• The Core Reduction: LPS(s) is equivalent to LCS(s, reverse(s)). Any common subsequence of a string and its reverse must be a palindrome.
• Implementation: Solving LPS is as simple as creating a reversed copy of the input string and passing both strings to your existing LCS function.
• Complexity: The time complexity is $O(N^2)$. The space complexity is $O(N^2)$ for the standard approach (which allows reconstruction) or $O(N)$ for the space-optimized version (which only finds the length).

We are continuing to build a strong foundation in dynamic programming on sequences. In our next lesson, we will tackle another classic problem in this category: the Longest Increasing Subsequence, which will introduce yet another distinct DP pattern.