Longest Palindromic Subsequence

You are given a string s consisting of lowercase English letters. Your task is to compute the length of the longest palindromic subsequence that can be extracted from s. A subsequence is obtained by deleting zero or more characters from the original string without changing the order of the remaining characters.

The dynamic programming approach uses the following recurrence relations:

• If s[i] == s[j], then for i<j: $$dp[i][j] = \begin{cases} 2 & \text{if } j-i+1=2,\\ dp[i+1][j-1] + 2 & \text{otherwise.} \end{cases}$$
• If s[i] != s[j], then $$dp[i][j] = \max(dp[i+1][j],\; dp[i][j-1]).$$

Every single character is considered a palindrome of length 1. For example, in the string abacdfg, one of the longest palindromic subsequences is aba, which has a length of 3.

inputFormat

The input consists of a single line containing a non-empty string s composed exclusively of lowercase English letters. The length of s does not exceed 1000.

outputFormat

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

a

1