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`

### Example 1

**Input**

s = "tacocat"

**Output**

10

**Explanation**

The palindromic substrings are:

`"t"`

`"a"`

`"c"`

`"o"`

`"c"`

`"a"`

`"t"`

`"coc"`

`"acoca"`

`"tacocat"`

Here is an easy/naive approach.

Start with a position i. Check if string of i-1, i, i+1 is a palindrome; continue expanding if still valid. Once found the longest possible palindrome with the center of i, simply get its length and divide by 2 for the number of palindromes.

The above is for palindrome of odd lengths, what about even length ones? We can pick i, and i+1 as a start. If it is a palindrome then continue expanding. The rest is the same.