Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
Examples
Input: s = "abc" Output: 3
Input: s = "aaa" Output: 6
Constraints
- 1 <= s.length <= 1,000
- s consists of lowercase English letters.