LPS  Longest Palindromic Substring
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, 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
Input: 5 ababa Output: 5
hide comments
sxie12:
20220917 23:46:06
Input format is not correct. n is not the same as the length of the string. 

ahmed_samir13:
20220610 04:43:31
Dp overall Complexity O(n^2) Tle


aknov711:
20210302 04:11:49
Solved it with hashing + binary search. Really a nice problem to begin with hashing! 

odysseus96:
20210118 10:12:24
i don't understand why do I keep getting WA on test case 15??


maskmanlucifer:
20201224 13:19:54
Use Mancher's algo 

fairoozr:
20201220 06:48:13
I used hashing+binary search, got a lot of WA, then replaced string with char [ ], it got AC. Very weird! And also I declared the arrays 5e5 instead of 1e5, and replaced n by strlen(s), as I got comments about the length and n not being the same in all test cases! Hope this helps anyone who face same problem as me! Last edit: 20201220 06:48:51 

lotte10:
20200616 10:13:12
Those who gave a try to solve with hashes, why are you complaining about WA ? That is probably collision, which is pretty obvious 

the_lizard_man:
20200305 15:34:54
tle .. with DP>n^2 

fahimcp495:
20200101 20:43:03
AC using manacher's algo 

maruf_1604089:
20191223 06:29:10
AC in 1 go using Palindrome Tree 
Added by:  Srivatsan B 
Date:  20090604 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  http://opc.iarcs.org.in/problems/iarcsfeb05ad1 