Longest Palindromic Subsequence

You are given a string \(s\) consisting of lowercase English letters. Your task is to determine the length of the longest palindromic subsequence in \(s\). A subsequence is a sequence that can be derived from the string by deleting some or no characters without changing the order of the remaining characters.

For example, if \(s = \texttt{bbabcbcab}\), one of the longest palindromic subsequences is \(\texttt{babcbab}\) which has a length of 7.

Note: A single character is considered a palindrome of length 1.

inputFormat

The input consists of a single line containing the string \(s\) (where \(1 \leq |s| \leq 1000\)), which is comprised only of lowercase English letters.

outputFormat

Output a single integer representing the length of the longest palindromic subsequence in the string \(s\).

bbabcbcab

7