Longest Palindromic Subsequence of Integer Digits

Given a positive integer, your task is to compute the length of the longest palindromic subsequence among its digits. A subsequence is a sequence derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. For instance, the integer 12321 contains the subsequence 12321 itself which is a palindrome of length 5.

We can solve this problem using dynamic programming. The recurrence for the DP solution is formulated as follows:

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

Read the integer from standard input and output the computed length to standard output.

inputFormat

The input consists of a single positive integer provided via standard input (stdin).

outputFormat

Output a single integer representing the length of the longest palindromic subsequence among the digits of the given integer to standard output (stdout).## sample

12321

5