Longest Palindromic Subsequence
Given a string s, find the length of its longest palindromic subsequence.
A subsequence is what remains after deleting some characters (possibly none) without reordering the rest, so unlike a substring it may skip. A palindrome reads the same forwards and backwards.
Input & Output
Input
s — the input string
Output
the length of the longest palindromic subsequence in s
Example
Input
s = "bbbab"
Output
4
Explanation
Deleting the 'a' leaves "bbbb", which reads the same both ways. No longer palindromic subsequence exists, so the answer is 4.
Example
Input
s = "abacb"
Output
3
Explanation
Keeping indices 0, 1, and 2 gives "aba". Nothing of length 4 works here, so the answer is 3.
Constraints
1 <= s.length <= 1000sconsists of lowercase English letters