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.

Expected approach

• Expand around center: for each of the 2n−1 centers (each char and each gap), expand outward while the ends match, incrementing the count per successful expansion. O(n^2) time, O(1) space — the expected interview answer. Alternatives to mention: DP table isPal[i][j] (O(n^2) time and space), and Manacher's algorithm for O(n) if pushed on optimality.