Number of Palindromic Substrings

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

Constraints

• 1 ≤ n ≤ 1,000 where n is the length of s

https://binarysearch.com/problems/Number-of-Palindromic-Substrings

Examples

Example 1

Input

• s = tacocat

Output

• answer = 10

Explanation

The palindromic substrings are:

• "t"
• "a"
• "c"
• "o"
• "c"
• "a"
• "t"
• "coc"
• "acoca"
• "tacocat"

Solution