Palindromic Substrings

Palindromic Substrings asks you to count every substring that reads the same forwards and backwards. It is the cleanest place to learn the expand-around-center technique — a pattern that also unlocks the harder "longest palindromic substring."

The slow way first

The obvious idea: generate every substring and check each one for being a palindrome. There are about O(n²) substrings, and checking each costs up to O(n), so this is O(n³) — far too slow for a long string.

The question to ask: what shape does a palindrome have? It is symmetric around its center. So instead of testing arbitrary substrings, we can start from each possible center and grow outward only as long as the two ends match.

The idea: expand around every center

A palindrome has a center. For an odd-length palindrome the center is a single character; for an even-length one it sits between two characters. A string of length n therefore has 2n − 1 centers. From each center, push lo left and hi right: every time s[lo] == s[hi] you have found one more palindrome, so bump the count and keep going. Stop the moment the ends differ or fall off the string.

The key insight: each successful expansion is a distinct palindrome, so we count as we expand — no separate palindrome check is ever needed.

Walk through it

Step through the animation on "aaa". The pointers lo and hi mark the current center and slide apart as it grows. The count ticks up each time both ends match: three single-character palindromes, two "aa" pairs, and one "aaa" — 6 total.

Pseudocode

count = 0
for each center position c:
    expand(c, c)        # odd-length center
    expand(c, c + 1)    # even-length center
return count
 
expand(lo, hi):
    while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
        count += 1                  # this slice is a palindrome
        lo -= 1                     # widen left
        hi += 1                     # widen right

The Python solution

def count_substrings(s):
    def expand(lo, hi):
        found = 0
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            found += 1
            lo -= 1
            hi += 1
        return found
    count = 0
    for c in range(len(s)):
        count += expand(c, c)
        count += expand(c, c + 1)
    return count

• expand(lo, hi) grows outward from a center and returns how many palindromes it found.
• The while condition has three guards: stay on the string (lo >= 0, hi < len(s)) and the ends must match (s[lo] == s[hi]).
• Each loop iteration means the current slice is a palindrome, so we do found += 1 before widening.
• For each index c we call expand twice: (c, c) for odd-length centers and (c, c + 1) for even-length ones.
• The two calls cover all 2n − 1 centers, so every palindrome is counted exactly once.

Complexity

We drop from O(n³) to O(n²) and use only O(1) extra space — just a couple of pointers and a counter. (An even faster O(n) algorithm called Manacher's exists, but expand-around-center is what interviewers expect.)

When this pattern shows up

Practice