Count All Palindromic Substrings

Problem Count all palindromic substrings of a string — every contiguous substring that reads the same forwards and backwards, counting single characters and counting each occurrence separately.

Input / Output

• Input: string s.
• Output: integer count of palindromic substrings.

Constraints

• |s| up to 10^4 for O(n^2); Manacher's handles 10^6.

Example

• s = "aaa" → 6 ("a"×3, "aa"×2, "aaa").
• s = "abc" → 3.