Longest Palindromic Subsequence

The key idea

A subsequence keeps order but can skip characters. The longest palindromic subsequence of s is the longest common subsequence of s and its reverse — but the cleaner view is interval DP: when the two ends of a window match, they wrap a palindrome of the inside plus 2; when they differ, drop one end and keep the better side.

Problem

Given a string s, find the length of the longest palindromic subsequence in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

A string is a palindrome when it reads the same forwards and backwards. Return only the length of the longest such subsequence, not the subsequence itself.

Constraints

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

Examples

Input: s = "bbbab" Output: 4

Input: s = "cbbd" Output: 2

Complexity

Time: O(n^2) Space: O(n^2)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →