Longest Palindromic Subsequence

Given a string s, your task is to compute the length of the longest palindromic subsequence in 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.

The solution should use a dynamic programming approach to ensure optimal performance. Note that the input string may have repeated characters and can be of varying length.

For example, in the string "bbbab", one of the longest palindromic subsequences is "bbbb" which has a length of 4.

Mathematical Formulation:

Let dp[i][j] denote the length of the longest palindromic subsequence in the substring \( s[i \ldots j] \). The recurrence relations are:

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

inputFormat

The input consists of a single line containing a string s.

You should read the string from standard input (stdin).

outputFormat

Output the length of the longest palindromic subsequence as an integer. The result should be written to standard output (stdout).

bbbab

4