Longest Palindromic Subsequence
What you'll learn: How to find the length of the longest palindromic subsequence in a string using a 2D dynamic programming table.
The Core Idea
A palindromic subsequence is a sequence of characters that reads the same forwards and backwards, but doesn't need to be contiguous. For example, in the string "BBABCBCAB", the subsequence "BABCBAB" is a palindrome.
The key insight: if characters at both ends of a substring match, they can both be included in the palindrome. If they don't match, we must choose which end to exclude and take the better result.
The DP Approach
We use a 2D table dp[i][j] where each cell represents the length of the longest palindromic subsequence in the substring from index i to index j.
State transition logic:
- If
s[i] == s[j]: the characters match, sodp[i][j] = dp[i+1][j-1] + 2 - If
s[i] != s[j]: take the maximum of excluding either end:dp[i][j] = max(dp[i+1][j], dp[i][j-1])
Base cases:
- Single character:
dp[i][i] = 1(every character is a palindrome by itself) - Build from smaller substrings to larger ones
Why This Works
Think of it like peeling an onion from the outside in. If the outer layer matches, keep both sides and look at the inner problem. If not, try peeling from the left, try peeling from the right, and take whichever gives the longer palindrome.
The overlapping subproblems (same substrings checked multiple times) and optimal substructure (optimal solution contains optimal solutions to subproblems) make this perfect for DP.
Key Takeaway: Longest Palindromic Subsequence uses a 2D DP table where matching end characters contribute 2 to the length, and mismatches require choosing the better of two recursive subproblems—building solutions from smaller substrings upward.