Longest Palindromic Subsequence LeetCode: DP Walkthrough

Longest Palindromic Subsequence (LeetCode #516) is one of the most elegant 2D dynamic programming problems you will encounter. The problem asks for the length of the longest subsequence of a string that reads the same forwards and backwards.

What makes this problem special is a beautiful insight: the longest palindromic subsequence of a string s is exactly the longest common subsequence of s and its reverse. If you have already solved LCS (#1143), you can reuse the exact same approach here.

In this walkthrough, we will cover both the LCS reduction trick and the direct DP formulation so you have two ways to think about the problem.

Given a string s, find the length of the longest subsequence that is a palindrome. A subsequence is a sequence that can be derived from the string by deleting some (or no) characters without changing the order of the remaining characters.

For example, given "bbbab", the longest palindromic subsequence is "bbbb" with length 4. You skip the "a" and the remaining "bbbb" reads the same forwards and backwards.

Another example: "cbbd" has a longest palindromic subsequence of "bb" with length 2. No longer palindromic subsequence exists in this string.

Here is the key insight that makes this problem approachable: LPS(s) = LCS(s, reverse(s)). The longest palindromic subsequence of any string equals the longest common subsequence between that string and its reverse.

Why does this work? A palindrome reads the same forwards and backwards. So any subsequence that appears in both the original string and its reverse must, by definition, be a palindromic subsequence. The longest such shared subsequence is the longest palindromic subsequence.

This means if you have already implemented Longest Common Subsequence (#1143), you can solve LeetCode 516 with one extra line — just reverse the string and call your LCS function. The time and space complexity remain O(n^2), same as standard LCS.

You can also solve longest palindromic subsequence LeetCode #516 directly without reducing to LCS. Define dp[i][j] as the length of the longest palindromic subsequence in the substring s[i..j].

The recurrence is straightforward. If s[i] equals s[j], then those two characters can bookend a palindrome: dp[i][j] = 2 + dp[i+1][j-1]. If they are not equal, take the better of excluding either end: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

The base cases are simple: every single character is a palindrome of length 1, so dp[i][i] = 1 for all i. Fill the table diagonally from shorter substrings to longer ones.

Let us trace through "bbbab" step by step. Every single character starts with dp[i][i] = 1. For the substring "bb" (indices 0-1), s[0] == s[1] so dp[0][1] = 2 + dp[1][0] = 2. Continue filling the table diagonally.

When we reach dp[0][4] for the full string "bbbab", the characters s[0]="b" and s[4]="b" match, giving dp[0][4] = 2 + dp[1][3]. Working through dp[1][3] for "bba", s[1]="b" does not equal s[3]="a", so dp[1][3] = max(dp[2][3], dp[1][2]) = max(1, 2) = 2. Therefore dp[0][4] = 2 + 2 = 4. The LPS is "bbbb".

For "cbbd": s[0]="c" and s[3]="d" do not match. We check dp[1][3] for "bbd" and dp[0][2] for "cbb". Both subproblems yield 2 (from "bb"). So dp[0][3] = 2, and the LPS is "bb".

Single character strings always return 1 — a single character is trivially a palindrome. This is the minimum possible answer since the problem guarantees the string is non-empty.

If all characters are the same (like "aaaa"), the entire string is a palindrome and the answer is n. This is the maximum possible answer.

There is no case where the answer is 0. Every non-empty string has at least one palindromic subsequence of length 1 (any single character). This is a useful sanity check for your implementation.

This problem is a masterclass in 2D string DP. You learn to define subproblems over ranges (i, j) and fill a table diagonally. This same pattern appears in problems like Minimum Insertions to Make Palindrome and Palindrome Partitioning.

The LCS reduction trick is equally valuable. Recognizing that a new problem is equivalent to one you have already solved is a powerful interview skill. It shows depth of understanding rather than just memorization.

Understanding the difference between palindromic subsequence and palindromic substring is essential for interview success. Subsequence problems use DP tables, while substring problems often use expand-around-center or Manacher's algorithm. Review both with YeetCode flashcards to keep the distinctions sharp.