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.



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'. 



A single line with an integer representing the length of longest palindromic substring.







hide comments
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

maruf_1604089: 2019-12-23 06:29:10

AC in 1 go using Palindrome Tree

mac1309: 2019-07-27 08:10:57

suffix array implementation ending up in segmentation fault. http://p.ip.fi/IbuM

Help please

beingbmc: 2019-07-01 21:49:47

Used manacher's.
AC in first go!

ac5769: 2018-11-16 05:27:16

Last edit: 2018-11-16 05:27:40
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.

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?

Added by:Srivatsan B
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET