Longest Palindromic Subsequence (LeetCode 516)

The problem

Given a string s (at least one character), return the length of its longest palindromic subsequence: the longest palindrome you can get by deleting zero or more characters without reordering the rest.

Input:  s = "bbbab"
Output: 4

Delete the 'a' to get "bbbb", which is a palindrome of length 4.

How to think about it

Start with brute force. Generate all 2ⁿ subsequences and keep the longest palindrome. That is O(2ⁿ · n).

Why centre expansion doesn’t work here. For substrings you could grow from the middle, because the palindrome must be contiguous. A subsequence can skip characters, so there is no single centre to expand from. You need a table.

The key insight: look at the two ends of a range. Let dp[i][j] be the answer for the substring s[i..j]. If s[i] == s[j], those two characters can wrap whatever is best inside: dp[i][j] = dp[i+1][j-1] + 2. If they differ, at least one end is unused, so dp[i][j] = max(dp[i+1][j], dp[i][j-1]). A single character is a palindrome of length 1.

Fill in the right order. dp[i][j] needs dp[i+1][…], the row below. So loop i from the end backwards, and j from i + 1 forwards. This is the interval-DP shape: answers for short ranges build answers for long ones.

Which pattern is this? 2-D interval DP. The tell is “best palindrome subsequence” or any problem where the answer for a range comes from shrinking it at either end. It’s also the LCS of s and reverse(s).

Approach

1. Make an n × n table of zeros.
2. For i from n - 1 down to 0: set dp[i][i] = 1. Then for j from i + 1 to n - 1:
   • 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]).
3. Return dp[0][n-1].

Solution

def longest_palin_subseq(s):
    n = len(s); dp = [[0]*n for _ in range(n)]    # dp[i][j] = answer for s[i..j]
    for i in range(n-1, -1, -1):                  # bottom-up: shorter ranges first
        dp[i][i] = 1
        for j in range(i+1, n):
            if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2         # ends match: wrap the inside
            else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])          # drop one end
    return dp[0][n-1]
# longest_palin_subseq("bbbab") -> 4  ("bbbb")

When j = i + 1 and the two characters match, dp[i+1][j-1] is the cell below the diagonal, which is 0, so the pair correctly scores 2.

Dry run

On s = "bbbab", row i of the table once it is finished (columns j = 0..4):

For example, dp[2][4] covers "bab": the ends match, so it’s dp[3][3] + 2 = 3. The answer is dp[0][4] = 4.

Complexity

• Time: O(n²). Each of the n²/2 cells with i ≤ j takes constant time.
• Space: O(n²) for the table. Since row i only reads row i + 1, two rows (O(n)) are enough.

Edge cases and pitfalls

• Empty string isn’t allowed by the constraints; this code would fail on dp[0][-1] with n = 0, so guard it if your input can be empty.
• One character returns 1; all distinct returns 1.
• Wrong loop direction. Looping i forwards reads dp[i+1] before it’s filled.
• Confusing it with the substring version. "bbbab" has a longest palindromic substring of length 3 ("bbb" or "bab"), but the subsequence answer is 4.

Related problems

• Longest Palindromic Substring (LeetCode 5): the contiguous version, solved by expanding around centres.
• Longest Common Subsequence (LeetCode 1143): run it on s and s[::-1] for the same answer.
• Burst Balloons (LeetCode 312): a harder interval DP that also builds long ranges from short ones.