Longest Palindromic Subsequence in a Binary String

You are given a binary string consisting only of the characters 0 and 1. Your task is to compute the length of the longest palindromic subsequence in the string.

A palindromic subsequence is a sequence of characters that appears in the same order in the string (not necessarily contiguous) and reads the same forwards and backwards. For instance, in the string 110010, one such subsequence is "1001", which has a length of 4.

Your solution should use dynamic programming to efficiently determine the answer. The input will be provided via standard input (stdin) and the corresponding output should be printed to standard output (stdout).

Note: If any mathematical expressions appear, they should be formatted in LaTeX. However, for this problem no specific LaTeX formulas are required.

inputFormat

The input consists of a single line containing a binary string (composed only of characters '0' and '1').

outputFormat

Output a single integer representing the length of the longest palindromic subsequence in the given string.## sample

110010

4