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.