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 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
Input: 5 ababa Output: 5
hide comments
|
androidbasha:
2024-05-02 08:02:58
make this for ac
|
|
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
|
|
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??
|
|
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 |
| 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 |
RSS