Given a lowercase alphabet string
s, return the number of palindromic substrings in
1 ≤ n ≤ 1,000where
nis the length of
s = "tacocat"
The palindromic substrings are:
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.
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