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
yousef_osama06: 2024-03-15 20:15:36

n is not the same as the length of the string

sxie12: 2022-09-17 23:46:06

Input format is not correct. n is not the same as the length of the string.

ahmed_samir13: 2022-06-10 04:43:31

Dp overall Complexity O(n^2) Tle
Rabin Karp + Binary Search overall Complexity O (n*log(n)) Acc
Mancher overall Complexity O(n) Acc

aknov711: 2021-03-02 04:11:49

Solved it with hashing + binary search. Really a nice problem to begin with hashing!

odysseus96: 2021-01-18 10:12:24

i don't understand why do I keep getting WA on test case 15??
my code: <snip>

Last edit: 2022-09-18 10:46:46
maskmanlucifer: 2020-12-24 13:19:54

Use Mancher's algo

fairoozr: 2020-12-20 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: 2020-12-20 06:48:51
lotte10: 2020-06-16 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: 2020-03-05 15:34:54

tle .. with DP->n^2

fahimcp495: 2020-01-01 20:43:03

AC using manacher's algo


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