Longest Palindromic Substring

Palindrome Linked List

Palindromic Substrings

Return the longest contiguous substring that is a palindrome.

Return the longest palindromic contiguous substring of `s`. If multiple answers have the same maximum length, return the one with the smallest starting index.

**Input / output**
- Input: `s: string`
- Output: longest palindrome

**Examples**
1. `"cbbd"` returns `"bb"`.
2. `"abaxyzzyxf"` returns `"xyzzyx"`.

**Constraints**
- `1 <= s.length <= 1,000`
- Comparisons are case-sensitive.

**Follow-up**
How do expand-around-center, dynamic programming, and Manacher's algorithm compare?

- Checking every substring for being a palindrome is `O(n^3)`.
- The clean, interview-friendly optimum is to expand around every possible center in `O(n^2)` time and `O(1)` space.
- A palindrome is fully described by its center, so we grow outward from each center and remember the longest match.

Choose an Approach

- From a center, move two pointers outward while the characters match and stay in bounds.
- Return the start and end indices of the widest palindrome found for that center.

Expand Around a Center

- There are `2n - 1` centers: one at each character (odd length) and one between each pair (even length).
- For each center, expand and update the best `(start, end)` window whenever a longer palindrome is found.

Track the Longest Over All Centers

- Each of the `2n - 1` centers expands at most `O(n)` times, so the total time is `O(n^2)`.
- We only store a couple of indices, so the extra space is `O(1)`.