Longest Palindromic Subsequence

Given a string S, your task is to determine the length of the Longest Palindromic Subsequence (LPS) within it.

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.

Mathematically, if S = s₁s₂...s_n, then the LPS is defined as the maximum length of any palindrome that is a subsequence of S. In formula form, this can be expressed as:

$$LPS(S) = \max\{|P| : P \text{ is a palindrome subsequence of } S\}$$

Your solution should use dynamic programming or any other appropriate method to achieve an efficient result.

inputFormat

The input consists of a single line containing a non-empty string S composed of lowercase English letters.

outputFormat

Output a single integer which is the length of the longest palindromic subsequence in S.

abacaba

7