Longest Palindromic Subsequence

Given a string s consisting of lowercase English letters, find the length of the longest subsequence that is also a palindrome.

A subsequence is obtained by deleting zero or more characters from the string without changing the order of the remaining characters. Formally, for a string \(s\), determine \(\text{LPS}(s)\), the length of the longest palindromic subsequence.

This can be solved using dynamic programming. Let \(dp[i][j]\) denote the length of the longest palindromic subsequence in the substring \(s[i \ldots j]\). The recurrence is:

• If \(s[i] = s[j]\), then \(dp[i][j] = dp[i+1][j-1] + 2\).
• Otherwise, \(dp[i][j] = \max(dp[i+1][j], dp[i][j-1])\).

The final answer is \(dp[0][n-1]\) where \(n\) is the length of \(s\).

inputFormat

Input is read from stdin. A single line containing the string s is given, where s consists only of lowercase English letters.

outputFormat

Output the length of the longest palindromic subsequence in s to stdout.

abba

4