Longest Palindromic Subsequence

Given a string s consisting of lowercase alphabets, your task is to determine the length of the longest palindromic subsequence in s. A palindromic subsequence is a sequence of characters that reads the same backward as forward and may not necessarily be contiguous.

You can solve this problem using a dynamic programming approach. One way to look at the recurrence is:

\( dp[i][j] = \begin{cases}
1 & \text{if } i = j, \\
2 & \text{if } s_i = s_j \text{ and } j = i+1, \\
dp[i+1][j-1] + 2 & \text{if } s_i = s_j, \\
\max(dp[i+1][j], dp[i][j-1]) & \text{if } s_i \neq s_j
\end{cases} \)

Your goal is to compute and output the length of the longest palindromic subsequence in the given string.

inputFormat

The input consists of a single line containing a string s made up of lowercase English letters.

outputFormat

Output a single integer which is the length of the longest palindromic subsequence in s.

bbabcbcab

7