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
gaurav117: 2015-09-29 04:38:36

is there some sort of error in the test cases since my same code (with some input output modifications) got ac in MSUBSTR ??

B@dsh@h: 2015-09-20 20:19:45

is string with space to be considered or not?

B@dsh@h: 2015-09-20 20:19:02

my solution is far correct but it gives me wrong ans...

José Carlos Gutiérrez: 2015-07-11 19:20:45

fix the statement, in input there are characters that are not lower case english letters...

Mohit Pandey: 2015-06-23 14:29:55

Wrong test cases!
1234xaba4321
AC sol gives ans 4!

Siddharth Singh: 2015-06-01 17:18:44

O(N^2) Solution not Passing with C :(

canhnht: 2015-04-29 10:48:43

tests like lol

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.


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