Palindromic Substrings

Count every continuous palindrome in a string.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Palindromic Substrings: Each successful radius around each odd or even center identifies exactly one distinct palindromic substring occurrence.

Input and goalCount every continuous palindrome in a string.

Initialize center sumFor aaa, the generator starts at middle 0 and the accumulated sum is 0.

next middle=0a0a1a2

inputaaarunningTotal0

Recognize it

The task counts contiguous palindrome occurrences, including equal text at different positions, so each center-radius pair should contribute separately.

Keep true

Each successful while iteration adds one new palindrome for that center and then expands one cell outward. Completed centers contribute disjoint occurrences because every palindrome has one unique center.

Reuse it

Map each combinatorial object to a unique center and radius, then count every successful expansion once; the same enumeration underlies longest-palindrome and palindrome-radius algorithms.

Pattern: Expand from every center.

Simple idea: This is the same center rule as Longest Palindromic Substring. Count each valid expansion instead of saving the longest one.

def count_palindromic_substrings(text: str) -> int:
   def expand(left: int, right: int) -> int:
      count = 0
      while left >= 0 and right < len(text) and text[left] == text[right]:
         count += 1
         left -= 1
         right += 1
      return count

   return sum(
      expand(middle, middle) + expand(middle, middle + 1)
      for middle in range(len(text))
   )

Cost: $O(n^2)$ time and $O(1)$ space.