Lv.4manacherstring
Longest Palindromic Substring
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Return the length of the longest palindromic contiguous substring of s.
Examples
| s | result |
|---|---|
"babad" | 3 |
"cbbd" | 2 |
"x" | 1 |
"forgeeksskeegfor" | 10 |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(s: string) → int
Constraints
-
s.length, lowercase English letters only
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| s | Expected |
|---|---|
"babad" | 3 |
"cbbd" | 2 |
"x" | 1 |
"forgeeksskeegfor" | 10 |
Hint
Hint
Expanding around every center is on inputs like "aaa…a". Manacher's algorithm reuses the mirror image inside the
rightmost palindrome found so far (insert separators to unify odd and even lengths), giving . Rolling hash with binary
search () also works.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 4 | inputs and outputs |
| correctness | 40 | 9 | verdict only |
| performance | 60 | 5 | verdict only |