[BS link]

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


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

Example 1


s = "tacocat"




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

Recommended Posts