Description
Given a string s, find the longest palindromic subsequence's length. A subsequence is a sequence derived by deleting some characters without changing order.
Examples
Input:
s = "bbbab"Output:
4Explanation:
One possible longest palindromic subsequence is "bbbb".
Input:
s = "abcde"Output:
1Explanation:
Since all characters are different, no palindromic subsequence longer than 1 can be formed. Any single character forms a palindromic subsequence of length 1.
Input:
s = "racecar"Output:
7Explanation:
The entire string "racecar" is already a palindrome, so the longest palindromic subsequence is the string itself with length 7.
Constraints
- •
1 ≤ s.length ≤ 1000 - •
s consists only of lowercase English letters.