Find the Longest Palindromic Substring in Linear Time
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `longest_palindromic_substring(s)` and achieve `O(n)` time.
Return the longest contiguous substring that reads the same forward and backward. If several longest palindromes exist, return the one with the smallest starting index.
### Constraints
- `0 <= len(s) <= 200000`
- `s` contains ASCII letters and digits.
- Return the empty string for empty input.
- Auxiliary space may be `O(n)`.
### Examples
- `"babad"` returns `"bab"` because it starts before the equally long `"aba"`.
- `"cbbd"` returns `"bb"`.
- `"a"` returns `"a"`.
```hint Exercise both parity cases
Include odd-length and even-length answers, an all-equal string, and a string with no palindrome longer than one character.
```
```hint Preserve the tie rule
Use a case with two different longest palindromes of equal length and verify that the earlier start wins.
```
Overview: Implement `longest_palindromic_substring(s)` and achieve `O(n)` time. 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 letters and digits, 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 letters and digits.
- 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: ('a',)
Expected Output: 'a'
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.