Given a lowercase alphabet string s
, return the number of palindromic substrings in s
.
Constraints
1 ≤ n ≤ 1,000
wheren
is the length ofs
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.