Longest Palindromic Subsequence: 2D Dynamic Programming

You are given a single string s. Find the length of the longest subsequence that reads the same forwards and backwards. A subsequence does not need to be contiguous - you can skip characters, but you cannot rearrange them.

This is LeetCode 516: Longest Palindromic Subsequence. Unlike Longest Palindromic Substring, which requires contiguous characters, this problem allows gaps. That changes the approach entirely: instead of expanding from centers, you need a 2D DP table that considers every possible substring of s.

The problem

Given a string s, return the length of the longest palindromic subsequence in s.

A few examples:

• s = "bbbab" returns 4. The longest palindromic subsequence is "bbbb".
• s = "cbbd" returns 2. The longest palindromic subsequence is "bb".

The approach

The key idea is interval DP. Define dp[i][j] as the length of the longest palindromic subsequence in the substring s[i..j]. You want dp[0][n-1], where n is the length of the string.

The recurrence depends on whether the endpoints of the current substring match:

1. If s[i] == s[j], those two characters can wrap around whatever palindromic subsequence exists inside them: dp[i][j] = dp[i+1][j-1] + 2
2. If s[i] != s[j], at least one endpoint is not part of the best subsequence. Try dropping each one and take the better result: dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The base case is simple: every single character is a palindrome of length 1, so dp[i][i] = 1 for all i.

Step-by-step walkthrough

Let's trace the algorithm on s = "bbbab". The DP table is a 5x5 grid where rows represent the start index i and columns represent the end index j. Only cells where i is at most j are valid.

Notice how the answer builds up from the diagonal. Each layer depends only on the layer below it (shorter substrings). By the time you reach dp[0][4], every subproblem it needs has already been solved.

The code

def longest_palindrome_subseq(s):
    n = len(s)
    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])

    return dp[0][n - 1]

Here is what each part does:

• Lines 2-3: Create an n x n table initialized to 0.
• Lines 5-6: Base case. Every single character is a palindrome of length 1.
• Line 8: Outer loop iterates by substring length, from 2 up to n.
• Line 9: Inner loop iterates over all starting positions i for the current length.
• Line 10: Compute the ending position j from i and length.
• Lines 11-12: If the endpoints match, take the inner subsequence length and add 2.
• Lines 13-14: If they do not match, take the better of dropping the left or right endpoint.
• Line 16: The answer is in dp[0][n-1], covering the full string.

Complexity analysis

Time: O(n^2). You fill roughly n^2 / 2 cells (the upper triangle of the table), and each cell takes O(1) work.

Space: O(n^2). The full 2D table. You can optimize to O(n) space by noticing that each row only depends on the row below it, so you only need to keep two rows at a time. But the 2D version is clearer and easier to debug.

Building blocks

This problem is built on two fundamental ideas that show up across many DP problems.

Interval DP pattern

Unlike most 2D DP problems where you iterate row by row (like Longest Common Subsequence or Edit Distance), interval DP iterates by substring length. The outer loop goes from length = 2 to length = n, and the inner loop slides a window of that length across the string. This guarantees that when you compute dp[i][j], the smaller subproblems dp[i+1][j-1], dp[i+1][j], and dp[i][j-1] are already filled.

This same iteration order appears in matrix chain multiplication, optimal binary search trees, and burst balloons. Once you recognize the pattern of "iterate by gap size," you can apply it to any problem where the answer for a range depends on answers for shorter ranges.

Palindrome character matching

The recurrence checks whether the two endpoints of the current substring match. If they do, both characters contribute to the palindrome, and you recurse on the interior. If they do not, you try dropping each endpoint independently. This match/no-match branching is the same structure you see in LCS, but applied to a single string comparing its own endpoints rather than two different strings.

Edge cases

• Single character: s = "a" returns 1. The base case handles this directly since dp[0][0] = 1.
• All identical characters: s = "aaaa" returns 4. Every character matches every other character, so the entire string is the palindromic subsequence.
• No repeated characters: s = "abcde" returns 1. No two characters match, so every max call just propagates the base case value of 1.
• Already a palindrome: s = "racecar" returns 7. The endpoints keep matching as you peel inward, so dp[0][6] = dp[1][5] + 2 = dp[2][4] + 4 = dp[3][3] + 6 = 1 + 6 = 7.

From understanding to recall

You have just walked through the interval DP table for the longest palindromic subsequence. The recurrence is clean: match means dp[i+1][j-1] + 2, no match means max(dp[i+1][j], dp[i][j-1]). The iteration order by substring length is what makes it work.

But knowing this while reading is different from producing it under pressure. In an interview, you need to remember the iteration order (by length, not by row), the correct index math for j = i + length - 1, and the base case on the diagonal. These are exactly the details that fade after a few days.

The interval DP pattern is one of roughly 60 reusable building blocks in the CodeBricks system. You drill each block individually with spaced repetition until writing the solution from scratch is automatic. Once interval DP is locked in, problems like palindrome partitioning and matrix chain multiplication become variations of the same idea rather than new problems to learn from scratch.

Related posts

• Longest Common Subsequence - The LPS problem can actually be reduced to LCS of s and reverse(s), connecting these two DP patterns
• Palindrome Partitioning II - Another interval DP problem on palindromes, minimizing cuts instead of maximizing subsequence length
• Longest Palindromic Substring - Finding the longest contiguous palindrome, a related but different problem