Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.

A substring is a contiguous sequence of characters within the string. A string is palindromic if it reads the same backward as forward.

Examples

Example 1:

Input: s = "abc"

Output: 3

Explanation: The three palindromic substrings are: "a", "b", "c".

Example 2:

Input: s = "aaa"

Output: 6

Explanation: The six palindromic substrings are: "a", "a", "a", "aa", "aa", "aaa".

Constraints

• 1 <= s.length <= 1000
• s consists of only lowercase English letters.