Palindromic Substrings

Longest Palindromic Substring

Palindrome String

Count every contiguous substring that reads the same forward and backward.

Count all palindromic contiguous substrings of `s`. Substrings with identical text at different positions count separately, and every single character is a palindrome.

**Input / output**
- Input: `s: string`
- Output: integer count

**Examples**
1. `"abc"` returns `3`.
2. `"aaa"` returns `6`: three single characters, two `"aa"` substrings, and one `"aaa"`.

**Constraints**
- `1 <= s.length <= 1,000`
- `s` contains lowercase English letters.

**Follow-up**
Explain why expanding around `2n - 1` centers is quadratic time but constant extra space.

- Every substring that reads the same forwards and backwards counts, including all single characters.
- Substrings at different positions are counted separately even if they look identical.
- A brute-force check of every substring is `O(n^3)`; we can do much better by growing palindromes from their centers.

Understand What Counts

- A palindrome is defined by its center. A string of length `n` has `2n - 1` possible centers: `n` single-character centers (odd-length palindromes) and `n - 1` between-character centers (even-length palindromes).
- From a center, expand outward while the characters on both sides match. Each successful expansion is one more palindromic substring.

Expand Around Each Center

- For each index `i`, count odd-length palindromes centered at `i` (`expand(i, i)`) and even-length palindromes centered between `i` and `i + 1` (`expand(i, i + 1)`).
- Add the two counts for every index.

Sum Odd and Even Centers

- Expanding around every center visits each of the `2n - 1` centers and expands at most `O(n)` times, giving `O(n^2)` time.
- Only a few counters are used, so the extra space is `O(1)`.