Eric Campbell 6 min read Engineering

Longest Palindromic Subsequence: DP Approach

Before diving into the algorithm, let's clarify terminology that trips up many engineers. A **subsequence** maintains relative order but allows gaps—from 'character', you can extract 'car' or 'chr'....

Key Insights

  • The Longest Palindromic Subsequence (LPS) problem reduces elegantly to finding the Longest Common Subsequence between a string and its reverse, revealing a powerful pattern-matching technique in dynamic programming.
  • A 2D DP table where dp[i][j] represents the LPS length for substring s[i..j] enables an O(n²) solution, but careful analysis allows space optimization to O(n) using only two rows.
  • Reconstructing the actual palindrome requires backtracking through the DP table, a skill that transfers directly to dozens of other DP problems.

Introduction & Problem Definition

Before diving into the algorithm, let’s clarify terminology that trips up many engineers. A subsequence maintains relative order but allows gaps—from “character”, you can extract “car” or “chr”. A substring must be contiguous—“char” works, but “car” doesn’t.

A palindromic subsequence reads the same forwards and backwards. For the string “bbbab”, the longest palindromic subsequence is “bbbb” with length 4. Note that “bbbab” itself isn’t a palindrome, but we can skip the ‘a’ to form one.

The problem: given a string s, find the length of its longest palindromic subsequence.

This isn’t just an interview question. DNA sequence analysis uses LPS to identify biological palindromes—sequences that read the same on complementary strands. Text compression algorithms exploit palindromic patterns for efficient encoding. Understanding LPS builds intuition for an entire class of string DP problems.

Brute Force Approach & Its Limitations

The naive approach generates all possible subsequences and checks each for palindrome properties. With n characters, we have 2^n subsequences (each character is either included or excluded).

def lps_brute_force(s: str) -> int:
    def is_palindrome(subseq: str) -> bool:
        return subseq == subseq[::-1]
    
    def generate_subsequences(index: int, current: str) -> int:
        if index == len(s):
            if is_palindrome(current):
                return len(current)
            return 0
        
        # Include current character or skip it
        include = generate_subsequences(index + 1, current + s[index])
        exclude = generate_subsequences(index + 1, current)
        return max(include, exclude)
    
    return generate_subsequences(0, "")

This runs in O(2^n) time with O(n) space for the recursion stack. For a 30-character string, that’s over a billion operations. Completely impractical.

A slightly smarter recursive approach works from both ends:

def lps_recursive(s: str, left: int, right: int) -> int:
    if left > right:
        return 0
    if left == right:
        return 1
    
    if s[left] == s[right]:
        return 2 + lps_recursive(s, left + 1, right - 1)
    
    return max(
        lps_recursive(s, left + 1, right),
        lps_recursive(s, left, right - 1)
    )

Still exponential. The recursion tree explodes because we solve the same subproblems repeatedly. This is where dynamic programming enters.

Dynamic Programming Intuition

Two properties make DP applicable here:

Overlapping Subproblems: Computing lps("bbbab", 0, 4) requires lps("bbbab", 1, 4) and lps("bbbab", 0, 3). Both of these need lps("bbbab", 1, 3). Without memoization, we compute identical subproblems exponentially many times.

Optimal Substructure: The LPS of a string depends on LPS solutions of its substrings. If the first and last characters match, the answer is 2 plus the LPS of the middle portion. If they don’t match, we take the maximum of excluding either endpoint.

Here’s a key insight that simplifies implementation: the LPS of string s equals the LCS (Longest Common Subsequence) of s and its reverse. Think about it—a palindrome reads identically forwards and backwards, so any common subsequence between a string and its reverse must be palindromic.

For “bbbab”, its reverse is “babbb”. The LCS is “bbbb”, which is exactly the LPS.

This reduction is elegant, but the direct 2D DP approach is more intuitive for understanding the problem’s structure.

Bottom-Up DP Solution

We build a 2D table where dp[i][j] stores the LPS length for substring s[i..j] (inclusive).

Base cases:

  • Single characters: dp[i][i] = 1 (every character is a palindrome of length 1)
  • Empty substrings: dp[i][j] = 0 when i > j

Recurrence relation:

  • If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
  • Otherwise: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The key is filling the table in the right order. We need dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] before computing dp[i][j]. This means we process by increasing substring length.

def longest_palindromic_subsequence(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    # dp[i][j] = LPS length for s[i..j]
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single characters
    for i in range(n):
        dp[i][i] = 1
    
    # Fill for increasing substring lengths
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    return dp[0][n - 1]

Walkthrough with “bbbab”:

Initial state (single characters):

    b  b  b  a  b
b   1  0  0  0  0
b   0  1  0  0  0
b   0  0  1  0  0
a   0  0  0  1  0
b   0  0  0  0  1

After processing length 2:

  • dp[0][1]: s[0]=‘b’ == s[1]=‘b’, so dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2
  • dp[1][2]: s[1]=‘b’ == s[2]=‘b’, so dp[1][2] = 2
  • dp[2][3]: s[2]=‘b’ != s[3]=‘a’, so dp[2][3] = max(dp[3][3], dp[2][2]) = 1
  • dp[3][4]: s[3]=‘a’ != s[4]=‘b’, so dp[3][4] = 1

Continuing this process, dp[0][4] = 4, representing “bbbb”.

Space Optimization

The full 2D table uses O(n²) space. Notice that computing row i only requires row i+1. We can reduce to O(n) space using two arrays.

def lps_space_optimized(s: str) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    # Current and previous rows
    dp = [0] * n
    
    for i in range(n - 1, -1, -1):
        new_dp = [0] * n
        new_dp[i] = 1  # Base case: single character
        
        for j in range(i + 1, n):
            if s[i] == s[j]:
                new_dp[j] = dp[j - 1] + 2
            else:
                new_dp[j] = max(dp[j], new_dp[j - 1])
        
        dp = new_dp
    
    return dp[n - 1]

We iterate i from right to left. For each i, we compute all j > i. The trick is that dp holds the previous row (i+1), and new_dp builds the current row (i). After each outer iteration, we swap.

This achieves O(n) space while maintaining O(n²) time.

Reconstructing the Actual Subsequence

Returning just the length is often insufficient. Here’s how to reconstruct the actual palindrome by backtracking through the DP table:

def get_longest_palindromic_subsequence(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    
    # Build the full DP table (need it for backtracking)
    dp = [[0] * n for _ in range(n)]
    
    for i in range(n):
        dp[i][i] = 1
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    # Backtrack to build the palindrome
    result = []
    i, j = 0, n - 1
    
    while i <= j:
        if i == j:
            result.append(s[i])
            break
        elif s[i] == s[j]:
            result.append(s[i])
            i += 1
            j -= 1
        elif dp[i + 1][j] > dp[i][j - 1]:
            i += 1
        else:
            j -= 1
    
    # Build palindrome: first half + reverse of first half (minus middle if odd)
    first_half = result
    if len(first_half) > 0 and dp[0][n-1] % 2 == 1:
        # Odd length: don't duplicate the middle character
        return ''.join(first_half) + ''.join(reversed(first_half[:-1]))
    else:
        return ''.join(first_half) + ''.join(reversed(first_half))

The backtracking logic follows the same decisions we made during table construction, but in reverse—when characters match, we include them; otherwise, we move toward the larger subproblem.

Complexity Analysis & Related Problems

Time Complexity: O(n²) for both the standard and space-optimized versions. We fill n² cells, each in O(1) time.

Space Complexity: O(n²) for the standard version (needed for reconstruction), O(n) for the optimized version (length only).

Related Problems:

  1. Longest Palindromic Substring (contiguous): Use expand-around-center or Manacher’s algorithm. Different problem, different techniques.

  2. Minimum Insertions to Make Palindrome: Answer is n - LPS(s). The characters not in the LPS need matching characters inserted.

  3. Minimum Deletions to Make Palindrome: Identical to minimum insertions—same formula applies.

  4. Palindrome Partitioning: Uses LPS concepts but requires different DP formulation.

The LPS problem is a gateway to understanding how string DP problems decompose. Master this, and you’ll recognize the patterns in dozens of variations. The key mental model: think about what happens at the boundaries (first and last characters), define your subproblems clearly, and ensure your iteration order respects dependencies.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.