Longest Palindromic Substring

Interview

Time limit2sMemory limit512 MB

Summary

Given a lowercase string of up to 100,000 characters, report the length of its longest palindromic substring.

Level: Medium7 of 10
Topics: String, String matching, Dynamic programming, Two pointers
Solved: No attempts yet

Problem

You are given a string $S$ consisting only of lowercase English letters. Write a program that finds the length of the longest substring of $S$ that is a palindrome.

A palindrome is a string that reads the same forward and backward. A substring is a contiguous part of $S$ .

Input

The first line contains the string $S$ , consisting only of lowercase English letters. The length of $S$ is at most $100\,000$ .

Output

Print the length of the longest substring of $S$ that is a palindrome.

Examples5

Example 1
Input
```
abab
```
Expected output
```
3
```
Example 2
Input
```
banana
```
Expected output
```
5
```
Example 3
Input
```
keepcoding
```
Expected output
```
2
```
Example 4
Input
```
online
```
Expected output
```
1
```
Example 5
Input
```
eevee
```
Expected output
```
5
```