Longest Palindromic Subsequence

Difficulty: 1700 3000 ms 128 MB

strings dp

Print the length of the longest subsequence of S that is a palindrome.

Input: one line with the string S.

Output: the longest palindromic subsequence length.

Constraints:

• 1 ≤ |S| ≤ 1000
• lowercase letters

Sample Tests

bbbab

4

abcd

1

Read the Editorial