Longest Palindromic Subsequence

Given a string S, your task is to find the length of the longest palindromic subsequence in 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. A palindrome is a sequence that reads the same backward as forward.

You can use dynamic programming to solve this problem. Let \( dp[i][j] \) denote the length of the longest palindromic subsequence in the substring \( S[i \ldots j] \). The recurrence is defined as follows:

• Base case: \( dp[i][i] = 1 \) for all valid i.
• If \( S[i] = S[j] \), then \( dp[i][j] = dp[i+1][j-1] + 2 \) (with a special case for substrings of length 2).
• If \( S[i] \neq S[j] \), then \( dp[i][j] = \max(dp[i+1][j], dp[i][j-1]) \).

Your goal is to implement a solution that reads the input string from stdin and outputs the length of the longest palindromic subsequence to stdout.

inputFormat

The input consists of a single line containing the string S. The string S does not contain spaces and can be assumed to have a moderate length.

outputFormat

Output a single integer, representing the length of the longest palindromic subsequence in the given string.

a

1