Number of Palindromic Substrings (BinarySearch)

[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

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