Longest Palindromic Substring

HardPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Longest Palindromic Substring. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output