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 elements without changing the order of the remaining characters.

For example, for \( s = \text{'bbbab'} \), one of the longest palindromic subsequences is \( \text{'bbbb'} \) and its length is 4.

You are required to implement an efficient solution using dynamic programming.

inputFormat

The input consists of a single line containing the string s.

You should read the input from standard input (stdin).

outputFormat

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

The answer should be printed to standard output (stdout).

bbbab

4