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
sifat_15: 2018-09-19 09:22:09

Hlw, @akash1518
I also try to implement the code the using Hashing+Binary Search .
But My Code get WA at 13th test Case.
Could you give any Critical Case for my code.
https://paste.ubuntu.com/p/SycFmFK4Nw/

akash1518: 2018-08-28 17:12:12

binary search +hashing (nlogn)
N=10^5 passes

neha__mishra: 2018-08-02 09:46:17

I tried many versions for this problem including dynamic programming but each of them gave wrong answer after test case 16 or 14 or 15 ........ I wonder if the test cases can be downloaded from somewhere or how to know about the critical test cases?

Shubhashsi Roy Dipta: 2018-04-12 13:58:47

Test case is weak
10
abcdefdcba

My AC code gives me 4
But the answer should be 1

ammen99: 2018-01-01 09:27:17

authors, please update the constraints in the problem statement, N can be as big as 5*10^5

Krishna Mohan: 2017-11-18 11:52:11

It seems like upper limit of n is not 10^5, but more than that

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!!


Added by:Srivatsan B
Date:2009-06-04
Time limit:0.100s-0.490s
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