Longest palindromic substring of a string

Given a string, return its longest substring that reads the same forwards and backwards.

Interface

Unless you agree on a different interface with the interviewer, assume:

• longest_palindrome(s: str) -> str — returns a longest palindromic substring. If several have the same length, return the one that starts first.

Example

longest_palindrome("babad")              ->  "bab"          # "aba" has the same length but starts later
longest_palindrome("cbbd")               ->  "bb"           # even length: the center is between two letters
longest_palindrome("forgeeksskeegfor")   ->  "geeksskeeg"
longest_palindrome("a")                  ->  "a"

Constraints

• 1 <= len(s) <= 1000. Characters are ASCII letters and digits.

Clarifying questions

• Substring (contiguous) or subsequence?
• Is the comparison case-sensitive?
• Should ties go to the first one, or is any longest one fine?
• Do you want the string, its length or its indices?

What a strong answer covers

• Expanding around each of the 2n - 1 centers (every letter and every gap between letters): O(n²) time, O(1) extra space.
• Why it beats the O(n³) brute force, and how it compares with an O(n²) table of is_pal[i][j] that also uses O(n²) memory.
• Handling odd and even lengths in one helper.
• Manacher's algorithm for O(n) time, explained at a high level if asked.
• Tests: one character, all characters equal, no palindrome longer than 1, the answer at either end.

Follow-ups

• Reach linear time. Sketch Manacher's algorithm.
• Count all palindromic substrings instead of finding the longest.
• Return the longest palindromic subsequence instead.