Find the Longest Palindromic Substring
Company: eBay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Return the longest contiguous substring that reads the same forward and backward.
## Function Contract
Implement `longest_palindromic_substring(s)` and return a string.
## Rules
- A single character is a palindrome.
- When multiple longest palindromes exist, return the one with the earliest starting index.
- The empty string returns the empty string.
- The expected solution should do better than enumerating and rechecking every substring.
## Constraints
- `0 <= len(s) <= 5000`.
- `s` contains printable ASCII characters.
- The implementation must finish within the stated limit without relying on a named algorithm supplied by the prompt.
## Examples
```text
s = "babad"
output = "bab"
```
`"aba"` has the same length, but `"bab"` starts earlier.
Overview: Return the longest contiguous palindromic substring efficiently, choosing the earliest starting candidate when multiple maximum-length answers exist and handling empty input explicitly.
Given a printable ASCII string s, return its longest contiguous substring that reads the same forward and backward. A single character is a palindrome. If several longest palindromes exist, return the one with the earliest starting index. Return the empty string for empty input. The solution should improve on enumerating and rechecking every possible substring.
Constraints
- 0 <= len(s) <= 5000.
- s contains printable ASCII characters.
- For equal maximum lengths, return the palindrome with the earliest starting index.
Examples
Input: ('babad',)
Expected Output: 'bab'
Explanation: Both bab and aba have length three, so the earlier bab wins.
Input: ('cbbd',)
Expected Output: 'bb'
Explanation: The longest palindrome has even length.
Hints
- A palindrome is determined by a character center or a gap center.
- Use starting index as the secondary comparison key when lengths tie.