Longest palindromic substring

Time limit0.5sMemory limit512 MB

Summary

Find the length of the longest contiguous substring of S that reads the same forwards and backwards.

Level: Medium7 of 10
Topics: String, Binary search, Hash map
Solved: No attempts yet

Problem

A palindrome is a string that reads the same forwards and backwards. For example, a, aa, and aba are palindromes, while ab is not.

Given a string $S$ , write a program that finds the length of the longest palindromic substring of $S$ . A substring here is a contiguous block of characters cut out of $S$ .

Input

The first line contains the string $S$ . $S$ consists of lowercase letters only, and its length is at least 1 and at most 100,000.

Output

Print the length of the longest palindromic substring on the first line.

Examples5

Example 1
Input
```
abcd
```
Expected output
```
1
```
Example 2
Input
```
abab
```
Expected output
```
3
```
Example 3
Input
```
dcabccd
```
Expected output
```
2
```
Example 4
Input
```
abcba
```
Expected output
```
5
```
Example 5
Input
```
aaaaa
```
Expected output
```
5
```