说明

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

输入格式

一行字符串 s

输出格式

一个整数，即最长的回文子序列的长度

样例

bbbab

4

提示

样例说明：

输入：s = "bbbab"

输出：4

解释：一个可能的最长回文子序列为 "bbbb" 。

数据范围：

1 <= s.length <= 1000
s 仅由小写英文字母组成