| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
||||||||
|
2024-05-02 08:02:58
make this for ac int n; string s; cin >> n >> s; n = s.size(); // this line for acceptance |
||||||||
|
2024-03-15 20:15:36
n is not the same as the length of the string |
||||||||
|
2022-09-17 23:46:06
Input format is not correct. n is not the same as the length of the string. |
||||||||
|
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 |
||||||||
|
2021-03-02 04:11:49
Solved it with hashing + binary search. Really a nice problem to begin with hashing! |
||||||||
|
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 |
||||||||
|
2020-12-24 13:19:54
Use Mancher's algo |
||||||||
|
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 |
||||||||
|
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 |
||||||||
|
2020-03-05 15:34:54
tle .. with DP->n^2 |
||||||||
RSS