Longest Palindromic Subsequence

Problem statement

A designer wants to keep a symmetric sequence of symbols from a damaged inscription. Symbols may be deleted from anywhere, but the retained symbols must preserve their original order and read the same backward. Your task Find the length of the longest palindromic subsequence of the string. Important details A subsequence does not have to be contiguous. A one-character subsequence is always a palindrome. Count the longest achievable length rather than the number of palindromes. Repeated symbols can be paired only in an order consistent with the original string. Worked example For bbbab, deleting the a leaves bbbb, a palindrome of length 4. The full string is not a palindrome, so the answer is 4.

Input format

One nonempty string.

Output format

Print the maximum palindromic subsequence length.

Constraints

1 <= length <= 1000; lowercase letters.

Sample input

bbbab

Sample output

4