Longest Palindromic Subsequence

Problem Return the length of the longest palindromic SUBSEQUENCE of s (not necessarily contiguous).

Input / Output

• Input: string s. Output: max palindromic subsequence length.

Constraints

• |s| up to 1000 → O(n^2) DP time/space.

Example

• "bbbab" → 4 ("bbbb"); "cbbd" → 2.

Expected approach

• Interval DP: dp[i][j] = LPS length in s[i..j]; s[i]==s[j] → 2 + dp[i+1][j−1], else max(dp[i+1][j], dp[i][j−1]); base dp[i][i]=1; fill by increasing span. O(n^2). Equivalent: LCS(s, reverse(s)) — know why it's valid here. Contrast with longest palindromic SUBSTRING (contiguity changes everything) — interviewers love that distinction. Space O(n) with rolling rows; min-insertions-to-palindrome = n − LPS as the classic corollary.