DP 28: Longest Palindromic Subsequence

This chapter explores how to find the Longest Palindromic Subsequence (LPS) of a given string. By leveraging the foundational concepts of the Longest Common Subsequence (LCS) problem, we can transform a seemingly distinct pattern matching problem into a standard dynamic programming workflow with minimal code changes.

1. Problem Statement: Understanding Palindromic Subsequences

Before jumping into the algorithm, let's break down the core definitions:

• Subsequence: A sequence derived from a string by deleting some or no characters without changing the relative order of the remaining characters (can be non-contiguous).
• Palindrome: A string that reads the same forwards and backwards (e.g., "aba", "bbabb").
• Longest Palindromic Subsequence: Among all possible palindromic subsequences that can be formed from a string, we want to find the one with the maximum length.

Example Walkthrough

Consider the input string:

s = "bbbab"

Possible subsequences of s include:

• "ab" (not a palindrome)
• "bb" (palindrome, length = 2)
• "bbb" (palindrome, length = 3)
• "bbbb" (palindrome, length = 4)
• "bab" (palindrome, length = 3)
• "bbabb" (palindrome, length = 5)

Among all palindromic subsequences, "bbabb" is the longest, giving an answer of 5.

2. The Naive Approach vs. The Insightful Pivot

Naive Brute Force

1. Generate all subsequences: Use recursion or the power-set method to generate every possible subsequence.
2. Check for palindrome: Iterate through each generated subsequence and verify if it reads identically backwards and forwards.
3. Pick the maximum: Keep track of the longest valid palindromic subsequence found.

Note: Generating all subsequences takes $O(2^N)$ time complexity, and checking each for palindromic properties adds extra overhead. This quickly becomes intractable for larger strings. Can we do better by mapping this to an existing problem?

3. Core Mental Model: Connecting LPS to LCS

To optimize this, let's examine what a palindrome truly means from a structural perspective.

Real-Life Analogy

Think of a palindrome as a mirror reflection. If you write a word on a piece of paper and hold it up to a mirror, the reflection matches the original text only if the word is symmetric (a palindrome).

Let's take our string s1:

s1 = "bbabcbcab"

If this string contains a palindromic subsequence, that subsequence reads the same from left-to-right (s1) and from right-to-left (the reverse of s1).

Let's define our second string s2 as the exact reverse of s1:

s1 = "bbabcbcab"
s2 = "bacbcbabb"  (Reverse of s1)

If we find the Longest Common Subsequence (LCS) between s1 and s2, any matching characters found in both strings in the exact same relative order will naturally form a palindrome, because s2 is the reversed version of s1.

4. Step-by-Step Problem Transformation

By reducing LPS to LCS, the algorithm simplifies dramatically:

1. Take the input string s.
2. Create a second string t which is the exact reverse of s.
3. Compute the Longest Common Subsequence (LCS) between s and t.
4. The length of the LCS between s and its reverse t is guaranteed to be the length of the Longest Palindromic Subsequence.

5. Implementation: Translating Concept into Code

Since we have already solved the Longest Common Subsequence (LCS) problem in earlier modules, we can directly reuse our robust LCS function and simply pass the string and its reverse.

C++ Code Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    int lcs(string text1, string text2) {
        int n = text1.length();
        int m = text2.length();
        
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                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[n][m];
    }

public:
    int longestPalindromeSubseq(string s) {
        string t = s;
        reverse(t.begin(), t.end());
        return lcs(s, t);
    }
};

6. Complexity Analysis

7. Summary and Key Takeaways

• Problem Reduction: Longest Palindromic Subsequence (LPS) is not a brand new algorithmic problem; it is a direct application of Longest Common Subsequence (LCS).
• The Mirror Trick: Reversing the input string allows us to search for matching elements that satisfy both forward constraints and backward mirror constraints simultaneously.
• Code Reuse: By leveraging an existing lcs() function, we avoid writing redundant dynamic programming tabulation code.
• Space Optimization: Just like standard LCS, the space complexity of the LPS solution can be optimized from $O(N^2)$ down to $O(N)$ by keeping track of only the previous and current rows during DP table generation.