Palindromic Substrings: Expand Around Center

LeetCode 647, Palindromic Substrings, asks you to count every palindromic substring in a given string. Not just the longest one. All of them. At first glance this feels like it could be O(n^3) or worse, but there is a clean O(n^2) approach called expand around center that makes the whole thing straightforward.

If you have already solved Valid Palindrome, you have the core building block. This problem just applies it from every possible center in the string.

The problem

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Examples:

• "abc" has 3 palindromic substrings: "a", "b", "c". Each single character counts.
• "aaa" has 6: "a" (three times), "aa" (twice), "aaa" (once).

Every single character is a palindrome on its own, so the answer is always at least n. The question is how many multi-character palindromes are hiding in the string.

Brute force: check every substring

The most direct approach is to generate every possible substring and check if it is a palindrome.

def count_substrings_brute(s):
    count = 0
    n = len(s)

    for i in range(n):
        for j in range(i, n):
            sub = s[i:j + 1]
            if sub == sub[::-1]:
                count += 1

    return count

There are O(n^2) substrings, and checking each one takes O(n) time in the worst case. That gives O(n^3) total. It works, but it is too slow for large inputs.

Expand around center: O(n^2)

Here is the key insight: every palindrome has a center. For odd-length palindromes like "aba", the center is a single character. For even-length palindromes like "abba", the center is the gap between two characters.

A string of length n has 2n - 1 possible centers: n character centers (odd-length) and n - 1 gap centers (even-length). From each center, you expand outward by moving two pointers in opposite directions. As long as the characters at both pointers match, you have found a palindrome. When they stop matching (or you hit a boundary), you move on to the next center.

def count_substrings(s):
    count = 0
    n = len(s)

    def expand(left, right):
        nonlocal count
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # odd-length palindromes
        expand(i, i + 1)  # even-length palindromes

    return count

That is the whole solution. The expand helper does the work: it starts at a center and walks outward, counting each palindrome it finds along the way. The outer loop calls it twice per index, once for odd-length and once for even-length palindromes.

Visual walkthrough

Let's trace the algorithm on "abcba". We will walk through each center and see which palindromic substrings we discover.

Notice how center 2 is the big one. Starting from "c", the expansion finds "bcb" and then "abcba". That is three palindromes from a single center. The expand function naturally discovers all of them because each successful expansion means another palindrome.

Why this works

The reason expand around center is correct comes down to a simple fact: every palindromic substring has exactly one center, and every center can produce at most one palindrome of each size. By trying every center, you cover every possible palindromic substring exactly once.

Think of it this way. If s[i..j] is a palindrome, then its center is at position (i + j) / 2. When the algorithm reaches that center, the expand function will find s[i..j] because every smaller palindrome centered at the same point is also valid (a sub-palindrome of a palindrome is also a palindrome, as long as it is centered at the same point). So nothing gets missed.

Why two expand calls per index?

This is the part that trips people up. A single character center like index 2 handles "c", "bcb", "abcba". But what about even-length palindromes like "bb" in "abba"? There is no single character at the center of "bb". The center falls between indices 1 and 2.

The solution is simple: call expand(i, i) for odd-length palindromes and expand(i, i + 1) for even-length palindromes. The first call starts with left == right (a single character, always a palindrome). The second call starts with left and right one apart, and only counts a palindrome if s[left] == s[right].

You could also think of this as iterating over 2n - 1 centers and mapping each to a (left, right) pair, but the two-call approach is cleaner to write and easier to remember.

Complexity analysis

Time: O(n^2). There are 2n - 1 centers. From each center, the expand function can move at most n/2 steps in each direction. In the worst case (a string of all identical characters like "aaaa"), every center expands as far as possible, and the total work is proportional to n^2.

Space: O(1). Two pointers and a counter. No auxiliary data structures.

There is also Manacher's algorithm which solves this in O(n), but it is rarely asked in interviews and significantly harder to implement. Expand around center is the sweet spot: easy to write, easy to explain, and fast enough.

The building blocks

Palindromic Substrings is built from one fundamental brick that you have already seen in other two pointer problems.

Opposite-end convergence

The expand function is the opposite-end convergence pattern running in reverse. Instead of starting at the extremes and moving inward (like in Valid Palindrome), you start at the center and move outward. But the core mechanic is the same: two pointers, symmetric movement, character comparison at each step.

The shape is:

1. Initialize left and right at (or near) the center.
2. While both pointers are in bounds and s[left] == s[right], you have a palindrome.
3. Move left one step left and right one step right.
4. Stop when the characters disagree or a pointer goes out of bounds.

This is the same skeleton that drives Valid Palindrome, Container With Most Water, and the inner loop of 3Sum. The only difference is the direction of traversal. Once you can write the expand helper from scratch without looking anything up, you own the building block.

Other problems that use opposite-end convergence:

• Valid Palindrome (converge inward, skip non-alphanumeric)
• Longest Palindromic Substring (same expand technique, track the longest instead of counting)
• Container With Most Water (move the shorter side inward)
• 3Sum (inner loop uses converging pointers on sorted subarray)

Common mistakes

Forgetting the even-length expand call. If you only call expand(i, i), you will miss every even-length palindrome. The string "aabb" has the palindrome "aa", which you would never find with odd-length centers alone.

Counting outside the while loop instead of inside. The expand function discovers multiple palindromes per center. If you only count once after the loop finishes, you undercount.

Off-by-one on the boundary check. The condition left >= 0 and right < n must come before s[left] == s[right] in the while loop. If you check the characters first, you will get an index error when a pointer goes out of bounds.

Returning n plus something. Some people try to start with count = n (for all single characters) and then only expand for multi-character palindromes. This works but is error-prone. The cleaner approach is to let the expand function handle single characters naturally, since expand(i, i) always counts the character at index i as a palindrome on its first iteration.

Reading about it is not enough

Palindromic substrings is a medium-difficulty problem, but the actual code is surprisingly short. The danger is that it looks so simple you assume you will remember it. But try writing the expand helper, the two calls per index, and the boundary checks from scratch in two weeks. The details slip away faster than you think.

The opposite-end convergence building block is the same one that powers Valid Palindrome, Longest Palindromic Substring, and several other problems. Drill it until the expand function is automatic. Then these problems stop being things you need to recall and start being things you can reconstruct from first principles.

Related posts

• Valid Palindrome - The foundational opposite-end convergence pattern applied to palindrome checking
• The Two Pointers Pattern - The general pattern behind the expand technique
• Container With Most Water - Another problem that uses converging pointers from opposite ends