Hidden Palindrome

Interview

Time limit2sMemory limit512 MB

Summary

Given a word of at most 40 lowercase letters, find the longest palindromic subsequence obtainable by deleting letters from the front and back.

Level: Medium4 of 10
Topics: Dynamic programming, String, Intervals, Recursion
Solved: No attempts yet

Problem

A palindrome reads the same forwards and backwards. For example, mom and anna are palindromes. A word with a single letter, such as a, is also a palindrome.

You are given one word. You can delete letters from the front of the word and from the back of the word. Find the greatest length you can leave behind while the remaining part is a palindrome. That length is the length of the longest palindrome contained in the word.

Input

The first line contains a string of lowercase English letters. Its length is at least 1 and at most 40.

Output

Print the number of letters in the longest palindrome contained in the given word.

Examples3

Example 1
Input
```
banana
```
Expected output
```
5
```
Example 2
Input
```
abracadabra
```
Expected output
```
3
```
Example 3
Input
```
abba
```
Expected output
```
4
```