#516

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Longest Palindromic Subsequence

Find the length of the longest palindromic subsequence in a string using precise state transition dynamic programming.

Problem Statement

Given a string s, determine the length of its longest palindromic subsequence. A subsequence can skip characters but must preserve the original order. For example, in s = "bbbab", the subsequence "bbbb" is valid and palindromic.

You must return an integer representing the maximum length of any palindromic subsequence within s. The solution should handle strings up to 1000 characters efficiently and account for all lowercase letters. Consider the effects of overlapping subproblems and optimal substructure in your approach.

Examples

Example 1

Input: s = "bbbab"

Output: 4

One possible longest palindromic subsequence is "bbbb".

Example 2

Input: s = "cbbd"

Output: 2

One possible longest palindromic subsequence is "bb".

Constraints

1 <= s.length <= 1000
s consists only of lowercase English letters.

Solution Approach

Dynamic Programming Table Construction

Define a 2D dp array where dp[i][j] represents the length of the longest palindromic subsequence from index i to j. Initialize single-character substrings with dp[i][i] = 1 since each character is a palindrome of length 1.

State Transition Updates

Iterate over substring lengths from 2 to n. If s[i] == s[j], update dp[i][j] = dp[i+1][j-1] + 2. Otherwise, set dp[i][j] = max(dp[i+1][j], dp[i][j-1]). This ensures each dp value correctly represents the longest subsequence for that range.

Final Result Extraction

After filling the table, dp[0][n-1] contains the length of the longest palindromic subsequence for the entire string. Return this value as the final answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to iterating all substring ranges and updating the dp table. Space complexity is O(n^2) for the dp array, though it can be optimized to O(n) using a single rolling array along diagonals.

What Interviewers Usually Probe

Expecting use of dynamic programming rather than brute force recursion due to overlapping subproblems.
Watch for correct handling of single-character substrings and matching endpoints.
Check that candidates optimize state transitions and avoid unnecessary recomputation.

Common Pitfalls or Variants

Common pitfalls

Confusing subsequence with substring, which leads to incorrect dp updates.
Failing to correctly initialize dp for single-character substrings.
Overwriting dp values too early, which can break dependencies for longer substrings.

Follow-up variants

Return the actual longest palindromic subsequence string, not just its length.
Compute the minimum number of deletions to make the string a palindrome using the same dp logic.
Handle strings with both uppercase and lowercase letters while maintaining the longest palindromic subsequence.

FAQ

What is the key pattern for solving Longest Palindromic Subsequence?

State transition dynamic programming is the core pattern; use dp[i][j] to track longest palindromic subsequences in substrings.

Can this problem be solved with recursion?

Yes, but naive recursion is inefficient; memoization or bottom-up dynamic programming avoids exponential runtime.

How do I handle single-character substrings?

Initialize dp[i][i] = 1 because each single character is a palindrome of length 1.

What if characters at the ends of a substring don't match?

Take the maximum of dp[i+1][j] and dp[i][j-1] to ensure the longest palindromic subsequence is preserved.

Can space complexity be optimized?

Yes, by using a rolling array along diagonals, space can be reduced from O(n^2) to O(n) while maintaining correctness.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][j]$ as the length of the longest palindromic subsequence from the $i$-th character to the $j$-th character in string $s$. Initially, $f[i][i] = 1$, and the values of other positions are all $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i + 1][j - 1] + 2
                else:
                    f[i][j] = max(f[i + 1][j], f[i][j - 1])
        return f[0][-1]

Continue Practicing

#514 freedom trail #488 zuma game #474 ones and zeroes