Longest Palindromic Subsequence

Given a string s, your task is to determine the length of the longest palindromic subsequence in s. A palindromic subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining characters, and which reads the same forwards and backwards.

The problem can be formally defined using a dynamic programming recurrence. Let \(dp[i][j]\) denote the length of the longest palindromic subsequence in the substring \(s[i \ldots j]\). Then, the recurrence is:

[ \text{if } s[i] = s[j]: \quad dp[i][j] = \begin{cases} 2 & \text{if } j - i + 1 = 2 \ dp[i+1][j-1] + 2 & \text{otherwise} \end{cases} ] [ \text{else}:\quad dp[i][j] = \max(dp[i+1][j],, dp[i][j-1]) ]

The answer is \(dp[0][n-1]\), where \(n\) is the length of the input string.

inputFormat

The input consists of a single line containing the string s (with no spaces). The string's length will be at least 1 and reasonably small to allow a dynamic programming solution.

outputFormat

Output a single integer that represents the length of the longest palindromic subsequence found in the given string.

bbabcbcab

7