Longest Palindromic Substring | Dataford Interview Questions

In a Steven Douglas Associates text-processing utility, implement a function that returns the longest contiguous substring of s that is a palindrome. A palindrome reads identically from left to right and right to left.

If multiple palindromic substrings have the maximum length, return the one with the smallest starting index. The match is case-sensitive, and spaces or punctuation are ordinary characters.

Formal Specification

Input: s, a Python string.
Output: A string containing the earliest longest palindromic substring.
For an empty input string, return "".

Your primary implementation must use Manacher's algorithm. It should run in linear time by reusing palindrome radii already discovered around a rightmost palindrome boundary.

Constraints

0 <= len(s) <= 200,000
s contains printable ASCII characters
Return the earliest substring when multiple longest palindromes exist
Do not reorder, lowercase, or otherwise normalize characters

Function Signature

def longest_palindrome(s):

Your question is Longest Palindromic Substring. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem