Find the Longest Palindromic Substring in Linear Time
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find the Longest Palindromic Substring in Linear Time
Implement `longest_palindrome(s)` and return the longest contiguous palindromic substring. If several have maximum length, return the one with smallest start index. Target `O(n)` time using Manacher's algorithm and `O(n)` space.
Constraints: `0 <= len(s) <= 200000`; `s` contains ASCII characters.
```hint Preserve tie behavior
Test both odd- and even-length answers and two longest answers that begin at different positions.
```
Overview: Implement `longest_palindrome(s)` and return the longest contiguous palindromic substring. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given a string containing ASCII characters, return its longest contiguous palindromic substring in O(n) time. If several maximum-length palindromes exist, return the one with the smallest starting index. Return the empty string for empty input.
Constraints
- 0 <= len(s) <= 200000.
- The string contains ASCII characters.
- Return a contiguous palindrome; equal maximum lengths use the smallest starting index, and empty input returns the empty string.
Examples
Input: ('',)
Expected Output: ''
Explanation: Empty input returns empty output.
Input: ('Q',)
Expected Output: 'Q'
Explanation: A singleton is its own palindrome.
Hints
- Test empty and singleton inputs, an all-equal string, and a string with no palindrome longer than one character.
- Include both odd-length and even-length longest palindromes.
- Use two different maximum-length palindromes beginning at different positions and verify the earlier one wins.