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