Count Palindromic Substrings
Problem statement
Given a string $s$, return the number of palindromic substrings in it. A substring is a contiguous sequence of characters; two substrings with different start or end indices count separately even if they are equal as strings.
Constraints:
- $1 \le \mathrm{len}(s) \le 1000$
- $s$ consists of lowercase English letters.
Examples:
- $s = $ "abc" $\to 3$ (each single character: "a", "b", "c").
- $s = $ "aaa" $\to 6$ ("a", "a", "a", "aa", "aa", "aaa").
Show hint
Instead of listing substrings and testing each, what single point is every palindrome built symmetrically around?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.