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 no. of characters in the string. 1 <= N <= 100000.

Second line is a string with N characters, where the characters are always lowercase english alphabets, ie '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
Duc: 2015-02-22 02:57:41

The test cases are pretty weak...

Utkarsh Saxena: 2015-01-15 22:51:07

i think the test cases are faulty... an accepted solution using wrong concept of suffix arrays gives 4 as output for abcdshitdcba

Dhruv: 2014-09-06 14:38:42

I getting WA after the judge runs test case 13. I even copied the solution from http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ and modified to suit the input/output format, still error after 13th testcase. Any pointers people?
I tried both C and java.

nour samir: 2014-09-01 01:28:33

hi everyone i try to solve this problem using suffix array and that is my solution in c++ http://ideone.com/dqNJY1
i get WA :\ but i can't handle case like that abcdcba the right answer is 1 but my code generate 3 :\
help plz

Ritesh Kumar Gupta: 2012-06-29 04:58:21

@All :: Guys I don't know why ,but the gets gives wrong answer .. I changed gets to scanf("%s",buffer) and got accepted.

Nagi Nahas: 2010-02-04 12:55:37

I got accepted, but for some reason I am getting "wrong answer" if I use getline() or cin.get() instead of the extraction operator >> . Not only "wrong answer" but also the code finishes in 0.00 seconds, indicating that it read a very small amount of data. I don't know why.

Last edit: 2010-02-04 12:56:34
Jorge Bernadas: 2009-10-27 07:10:20

@kk: My solution is correct and gave 1 as answer.

Ankit kumar jain: 2009-10-03 13:41:31

what will be the answer of "adfg".

Ankit kumar jain: 2009-10-03 13:22:56

what will be the answer of "abcd".
answer is one or zero.

[Trichromatic] XilinX: 2009-06-04 14:41:03

Another (almost same) problem PALIM is available in the classical section now.


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