Question
Longest Palindromic Substring
Shreyas loves exploring patterns in strings.
One day, he is given a string s and challenged to find the length of the longest substring that reads the same forwards and backwards — in other words, the longest palindromic substring.
Your task is to help Shreyas find this length.
Input
The first line contains an integer n — the length of the string s.
The second line contains the string s of length n.
The second line contains the string s of length n.
Output
Print a single integer — the length of the longest palindromic substring of s.
Example
Input
10
babadababa
Output
9
Explanation:
The longest palindromic substring has length 9 (e.g., "babadabab" or "abadababa").
10
babadababa
Output
9
Explanation:
The longest palindromic substring has length 9 (e.g., "babadabab" or "abadababa").