Longest Palindromic Subsequence

Given a string s, determine the length of the longest palindromic subsequence within 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.

This problem is commonly solved using dynamic programming. For a given string s with length n, you can define a 2D DP table where dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j]. The recurrence formulas are as follows:

\(\text{If } s[i]==s[j]:\)

• If i = j (the same character) then \(dp[i][j]=1\).
• If j = i+1 then \(dp[i][j]=2\).
• Otherwise, \(dp[i][j] = dp[i+1][j-1] + 2\).

Otherwise, \(dp[i][j] = \max(dp[i+1][j], dp[i][j-1])\).

Your program should read the input string from stdin and output the result to stdout.

inputFormat

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

Note: The string will only contain lowercase English letters.

outputFormat

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

## sample

character

5