17 lines (12 loc) · 339 Bytes

Problem 4: Longest Palindromic Substring (Manacher)

Problem Statement

Find the longest palindromic substring using Manacher's algorithm in O(n).

Input Format

A string s.

Output Format

The longest palindromic substring.

Constraints

1 <= len(s) <= 1000

Example

Input: s="babad"
Output: "bab" or "aba"