Sabbir's team is compressing sensor-log strings and wants the longest palindromic PATTERN (subsequence, not necessarily contiguous) hidden in a log. Given a string S, print the length of its longest palindromic subsequence.
Input
One string S.
Output
Length of the longest palindromic subsequence.
Constraints
1 ≤ |S| ≤ 2000
Sample Input
bbbab
Sample Output
4
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.