Funcia
Lv.4manacherstring

Longest Palindromic Substring

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Return the length of the longest palindromic contiguous substring of s.

Examples

sresult
"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

  • 1≤1 \le s.length ≤300,000\le 300{,}000, lowercase English letters only

Expected complexity

Time
O(N)
Space
O(N)

Examples

sExpected
"babad"3
"cbbd"2
"x"1
"forgeeksskeegfor"10

Hint

Hint

Expanding around every center is O(N2)O(N^2) 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 O(N)O(N). Rolling hash with binary search (O(Nlog⁡N)O(N \log N)) also works.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample04inputs and outputs
correctness409verdict only
performance605verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.