1166. Longest Palindromic Subsequence

Given a string s, return the length of its longest palindromic subsequence — the longest subsequence that reads the same forward and backward. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the length of the longest palindromic subsequence.

Examples

Input: {"s":"bbbab"}
Output: 4
Explanation: 'bbbb' is palindromic.

Input: {"s":"cbbd"}
Output: 2
Explanation: 'bb'.

Input: {"s":"a"}
Output: 1
Explanation: Single character.

Constraints

• 1<=|s|<=1000

Asked by