LPS - Longest Palindromic Substring

no tags 

A palindrome is a string that is the same as its reverse. Example "malayalam", "dad", "appa" etc. In this problem you are asked to find the length of the longest contiguous substring of a given string, which is a palindrome.

Input

The first line consists of a single integer N, the number of characters in the string. 1 <= N <= 100000.

Second line is a string with N characters, where the characters are always lowercase English letters, i.e. 'a' to 'z'.

Output

A single line with an integer representing the length of longest palindromic substring.

Example
Input:
5
ababa

Output:
5


hide comments
gustavonunes: 2017-07-24 23:34:03

getline gave me WA, cin Acc

revenant: 2016-12-03 12:13:49

Don't go for spoj toolkit ...it has some wrong code.......

alpha coder: 2016-10-06 19:03:30

something is wrong with input , n ! = length of the string .

Jamil Siam: 2016-09-11 13:57:06

Beware people! this problem has string length of around 150000 after test case 15!!

Bender N: 2016-07-28 21:07:41

In this problem n != length of the string!

Bender N: 2016-07-26 18:02:43

What is wrong with input data? It is definitely not a simple lowercase English string.

Last edit: 2016-07-26 23:28:58
anando_du: 2016-01-26 19:41:11

No Corner Test Case ... Straightforward Solution . O(n) algo passed with basic C code ... C++ using string got TLE

yogi9046: 2016-01-11 06:57:23

did anyone get it correct? any corner test cases

Pawankumar P: 2015-11-30 05:58:40

cin -> TLE.
scanf -> AC.
(Even with Manacher)

Last edit: 2015-11-30 05:58:53
Mayank Raj: 2015-10-26 15:05:24

It would be nice if spoj is more python friendly - python is the future my dear!


Added by:Srivatsan B
Date:2009-06-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:http://opc.iarcs.org.in/problems/iarcs-feb05-ad-1