Given a string s, return the length of the longest subsequence of s that reads the same forwards and backwards. A subsequence is obtained by deleting zero or more characters without changing the order of the remaining characters.
Input
s: a non-empty string
Output
The length of the longest palindromic subsequence of s.
Examples
Example 1
Inputs = "hello"
Output2
Explanation: "ll" is a palindromic subsequence of length 2.
Example 2
Inputs = "abcde"
Output1
Explanation: No two characters match, so the best is any single character.
Constraints
1 <= s.length <= 1000