A subsequence is formed by deleting zero or more characters without reordering the rest. A string is a palindrome if it reads the same left-to-right and right-to-left. Given a string s, find the length of its longest palindromic subsequence.
A single line: the string s of lowercase letters a-z.
A single integer: the length of the longest palindromic subsequence.
s <= 1000Example 1
Input
bbbab
Expected
4
Explanation
Deleting the single 'a' leaves "bbbb", a palindrome of length 4; nothing longer is possible, so the answer is 4.
Example 2
Input
cbbd
Expected
2
Explanation
The best palindromic subsequence is "bb" of length 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →