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.