Longest Palindromic Subsequence

Problem Statement

Given a string S of length N, find the length (and optionally the actual subsequence) of the longest substring that reads the same forwards and backwards. A subsequence is obtained by deleting zero or more characters without changing the order of the remaining characters.

Example:

• S = "racecar" → "racecar" (length 7, the entire string)
• S = "banana" → "aaa" (length 3)
• S = "abccda" → "acca" (length 4)
• S = "abc" → "a", "b", or "c" (length 1)

The problem asks for the length of this subsequence, though many solutions also reconstruct the actual palindrome itself.

Why Longest Palindromic Subsequence Matters

LPS appears in multiple real-world domains:

• Bioinformatics: DNA sequences are palindromic in important regulatory regions (restriction sites). Detecting long palindromic subsequences helps identify conserved or repetitive patterns that may affect gene expression.
• Text compression and edit distance: The edit distance between a string and its reverse can be computed via LPS. If a string has a long palindromic subsequence, only a few insertions or deletions may be needed to make it fully palindromic.
• RNA structure prediction: RNA molecules form secondary structures via base pairing; palindromic or self-complementary subsequences play a role in hairpin formation.
• String matching and pattern discovery: Identifying symmetries in data can reveal anomalies, repeated motifs, or structural properties of the input.

Core Insight: LPS via LCS Reduction

The most elegant insight is this: LPS(S) = LCS(S, reverse(S)), where LCS is the longest common subsequence. The intuition is profound:

• A palindromic subsequence reads the same forwards and backwards.
• If you compare the string with its reverse, the longest common part is precisely what reads the same in both directions.
• This reduces LPS to a well-known DP problem with O(N²) time and space.

Example: S = "banana", reverse(S) = "ananab". The LCS of "banana" and "ananab" includes the shared subsequences: "ana", "aaa". The longest is "aaa" (or "ana" depending on tracking), both of which are palindromes.

The LCS approach is elegant but uses O(N) space because you build a 2D table. The direct DP approach, described next, often offers cleaner indexing.

Direct DP Approach: Recurrence Relation

Define dp[i][j] as the length of the LPS in the substring S[i..j] (inclusive on both ends).

Base case: Any single character is a palindrome, so dp[i][i] = 1.

Recurrence:

• If S[i] == S[j], the characters at both ends match. Include them both and recurse on the interior: dp[i][j] = dp[i+1][j-1] + 2.
• If S[i] != S[j], they cannot both be in the palindrome. Try excluding each: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

Fill order: Since dp[i][j] depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1], iterate by increasing substring length (or by decreasing i for fixed j).

Example Walkthrough: Computing LPS for "abccda"

Let S = "abccda" (length 6). Build the DP table where entry dp[i][j] is the LPS length of S[i..j].

     a  b  c  c  d  a
  a  1  1  1  1  1  2
  b     1  1  1  1  1
  c        1  2  2  2
  c           1  1  1
  d              1  1
  a                 1

Key cells:

• dp[0][0] = 1 ("a" is a palindrome)
• dp[1][1] = 1 ("b")
• dp[2][3] = 2 ("cc" matches, so dp[3][2] + 2, but dp[3][2] is out of bounds; actually dp[2][3] = 2 because "cc" forms a palindrome)
• dp[0][5] = 2 ("a...a" at positions 0 and 5 match; interior "bccdb" has LPS 0, so result is 0 + 2 = 2, giving us "aa")

Tracing the logic more carefully: dp[0][5] checks if S[0] == S[5], which is 'a' == 'a', so dp[0][5] = dp[1][4] + 2. Now dp[1][4] checks "bccdb": 'b' != 'd', so max(dp[2][4], dp[1][3]). Continuing recursively gives us the final answer. The LPS for "abccda" is length 4 (e.g., "acca").

Complexity Analysis

Time Complexity: O(N²)

• The DP table has N² cells.
• Each cell is computed in O(1) time (simple comparisons and table lookups).
• Total: O(N²) across all cells.

Space Complexity: O(N²)

• We store an N × N DP table.
• No recursion stack (in bottom-up DP), but the table itself dominates space.
• For very large N (e.g., DNA sequences of millions of bases), this can be prohibitive.

Can we do better? The LCS reduction inherently requires O(N²) space; there is no known way to compute LPS faster asymptotically for the general case. However, for special cases (e.g., highly repetitive strings), or when only the length is needed (not the actual subsequence), space-optimized variants exist.

Implementation: Python Bottom-Up DP

def longest_palindromic_subsequence(s):
    n = len(s)
    if n == 0:
        return ""

    # dp[i][j] = length of LPS in s[i..j]
    dp = [[0] * n for _ in range(n)]

    # Every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1

    # Fill table by increasing substring length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                # Ends match: add 2 to the interior's LPS
                dp[i][j] = dp[i + 1][j - 1] + 2 if i + 1 <= j - 1 else 2
            else:
                # Ends don't match: take the better of excluding left or right
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

# Test
print(longest_palindromic_subsequence("banana"))      # 3
print(longest_palindromic_subsequence("racecar"))     # 7
print(longest_palindromic_subsequence("abccda"))      # 4

This computes the length of the LPS. To reconstruct the actual subsequence, trace back through the DP table: if s[i] == s[j] and dp[i][j] > dp[i+1][j-1], include both s[i] and s[j]; otherwise, move to whichever of dp[i+1][j] or dp[i][j-1] is larger.

Subsequence vs Substring: The Critical Distinction

This problem is often confused with the longest palindromic substring, so the distinction is worth emphasizing:

For "banana": the longest palindromic substring is "aba" (length 3), but the longest palindromic subsequence is also length 3 ("aaa"). For "abccda", the substring is "cc" or "acca" (if we count the whole sequence), but the subsequence is "acca" (length 4).

Real-World Use Cases

1. DNA Sequence Analysis: DNA palindromes are restriction sites where DNA-cutting enzymes (restriction endonucleases) recognize and cut the sequence. Identifying long palindromic subsequences helps predict where restriction sites might be, or flags conserved regulatory regions. A classic example is EcoRI, which recognizes GAATTC — a palindromic sequence.

2. RNA Folding and Secondary Structure: RNA forms hairpins and loops when complementary bases pair up. A palindromic subsequence (after accounting for base pairing rules, where A pairs with U and C pairs with G) suggests the RNA can fold back on itself. This is critical for understanding mRNA regulation and protein synthesis.

3. Edit Distance and String Similarity: The minimum number of edits (insertions, deletions, substitutions) to make a string a palindrome is related to its LPS. If LPS length is L and the string length is N, you need at least N − L deletions (or insertions) to create a palindrome.

4. Compression and Data Encoding: Palindromic patterns can be exploited in data compression schemes. Run-length encoding or dictionary-based methods can be tuned to detect and compress palindromic subsequences efficiently.

Optimizations and Variants

Space Optimization: If only the length is needed (not reconstruction), you can observe that dp[i][j] depends only on dp[i+1][*] (and dp[i][*-1]). With careful iteration order, you can reduce space from O(N²) to O(N). However, this makes reconstruction harder and is typically not the bottleneck.

LCS via Two Strings: Instead of building a single 2D DP table, compute LCS(S, reverse(S)) using a standard two-string LCS algorithm. Some implementations find this more intuitive, though the complexity remains O(N²) time and space.

Memoized Recursion: You can implement the recurrence relation top-down with memoization, computing only the subproblems actually needed. This is equivalent to bottom-up DP in terms of complexity but may be clearer in structure.

Probabilistic and Approximation Algorithms: For very large sequences where O(N²) is infeasible, randomized or heuristic methods can find approximate LPS in faster time, though they are rarely the first choice.

Key Takeaways

The longest palindromic subsequence reduces elegantly to longest common subsequence by comparing the string with its reverse, yielding an O(N²) DP solution. The direct DP recurrence — matching outer characters and recursing inward — offers an intuitive alternative. Both approaches are fundamental; LPS appears in bioinformatics (DNA restriction sites, RNA folding), text processing, and edit distance problems. Always distinguish subsequence (non-contiguous) from substring (contiguous), as the algorithms and complexities differ significantly.