Blind 75Medium

Palindromic Substrings — Count by Expanding Centers

Expand around every index and gap to count palindromic substrings without building a DP table.

Expand Around CenterStringCounting

View problem on LeetCode

Problem Statement

Return how many substrings of s are palindromes.

Why This Problem Matters

Counting palindromes builds intuition for symmetric expansions that reappear in harder problems.
Shows how to reuse the same core idea from longest-palindrome questions for counting.
Highlights how to eliminate quadratic auxiliary space compared with dynamic programming.

Thought Process

Identify palindrome structure

Every palindrome mirrors around a center, so expanding from centers covers every possibility exactly once.

Consider both parity cases

Single characters seed odd-length palindromes; adjacent pairs seed even-length ones.

Accumulate counts locally

Each expansion returns how many palindromes it saw, which you add to the global total.

Step-by-Step Reasoning

Initialise total = 0.
For each index i, expand around (i, i) for odd-length palindromes and add the count.
Expand around (i, i + 1) for even-length palindromes and add the count.
Return the accumulated total after processing all centers.

Dry Run

s = "aaa", center = 1 odd expansion

Expands to "aaa" counting 3 palindromes ("a", "aaa", middle "a").

s = "aaa", center = (0,1) even expansion

Counts "aa" plus the two single letters from overlap, yielding the remaining 3 palindromes.

Complexity Analysis

Time

O(n^2)

Space

O(1)

Why

Each expansion can traverse the string once and there are 2n centers.

Annotated Solution

JAVA

public class PalindromicSubstrings {
  public int countSubstrings(String s) {
    int total = 0;
    for (int center = 0; center < s.length(); center += 1) {
      total += expand(s, center, center);
      total += expand(s, center, center + 1);
    }
    return total;
  }

  private int expand(String s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
      count += 1;
      left -= 1;
      right += 1;
    }
    return count;
  }
}

Each expansion grows outward while the characters mirror, incrementing the total for every valid radius.

Common Pitfalls

Using a shared counter without resetting per call can leak results between test cases.
Forgetting the even-length center undercounts cases like "abba".
Breaking from the loop prematurely misses palindromes that extend past the first mismatch.

Follow-Up Questions

How would you list the distinct palindromic substrings rather than just counting them?
Can you adapt the expansion to work on a stream of characters?

Key Takeaways

Center expansion gives you dynamic programming level coverage with constant auxiliary space.

Counting problems often reuse the same traversal as search problems—only the accumulation changes.

Parity considerations (odd vs even) are crucial anytime symmetry is involved.