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

Constraints

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

### Example 1

#### Input

`s = "tacocat"`

`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.

### Python solution

``````class Solution:
def solve(self, s):

def trv(s, start, end):
while start >= 0 and end < len(s) and s[start]==s[end]:
start -=1
end +=1
return end - start - 1

ans = 0

for i in range(n := len(s)):
odds = trv(s, i, i)
evens = trv(s, i, i+1)
ans += (odds//2) + (evens//2)

ans += n

return ans``````