Longest Palindromic Subsequence

You are given a string S consisting of uppercase or lowercase letters. Your task is to determine the length of the longest palindromic subsequence of S.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindromic subsequence is a subsequence which reads the same backward as forward.

Input Format: A single line containing the string S.

Output Format: A single integer which is the length of the longest palindromic subsequence found in S.

Note: You are expected to implement an efficient solution, typically using dynamic programming. The recurrence relation can be described in LaTeX as follows:

\[ \text{if } S[i] = S[j]:\quad dp[i][j] = 2 + dp[i+1][j-1] \quad (\text{if } i+1 \leq j-1) \quad \text{or } 2 \quad (\text{if } i+1 > j-1) \] \[ \text{otherwise: } dp[i][j] = \max(dp[i+1][j], dp[i][j-1]) \]

inputFormat

The input will be given from stdin as a single line containing a non-empty string S.

outputFormat

Print out the length of the longest palindromic subsequence to stdout.

bbabcbcab

7