# Palindromic Substrings

> How to solve Palindromic Substrings: count every palindromic substring of a string using the same expand-and-reuse dynamic programming idea.

- Difficulty: Medium
- Category: Dynamic Programming
- Topics: String, Dynamic Programming
- Published 2026-08-21

## Problem

Given a string, count how many of its contiguous substrings are palindromes. Substrings are counted by position, so two substrings with identical characters but different starting points both count separately.

**Example.** For `"aaa"`, there are 6 palindromic substrings: the three single letters `"a"`, `"a"`, `"a"`, the two pairs `"aa"`, `"aa"`, and the full string `"aaa"`.

## Key idea

Testing every substring directly and verifying each one from scratch costs O(n) per substring across O(n²) substrings, which is cubic overall. As with Longest Palindromic Substring, the shortcut is that a substring is a palindrome exactly when its outer two characters match and the substring left after removing them is also a palindrome. So once shorter spans are known, longer spans can be checked in constant time each.

Fill a table by increasing substring length, marking each span as a palindrome using that recurrence, and add one to a running total every time a span comes out true. The equivalent center-expansion view is just as direct for counting: for each of the 2n - 1 possible centers (each character, and each gap between two characters), expand outward one step at a time, and count every successful expansion as one more palindrome, since a successful match at a given radius always corresponds to exactly one distinct palindromic substring.

## Solution

```typescript
function countSubstrings(s: string): number {
  let count = 0;

  for (let center = 0; center < s.length; center++) {
    count += expandAndCount(s, center, center); // odd-length palindromes centered here
    count += expandAndCount(s, center, center + 1); // even-length palindromes centered in the gap
  }

  return count;
}

function expandAndCount(s: string, left: number, right: number): number {
  let matches = 0;

  while (left >= 0 && right < s.length && s[left] === s[right]) {
    matches++; // each successful expansion is one more distinct palindrome
    left--;
    right++;
  }

  return matches;
}
```

## Complexity

- **Time:** O(n²). Every span (or every center-radius combination) is checked exactly once.
- **Space:** O(n²) for the table version; O(1) for the center-expansion version, which only needs a running count.

## Watch out for

- Every single character is its own palindrome and must be counted, even though it looks trivial.
- Even-length palindromes need centers placed between two characters, not just on individual characters.
- This is a counting problem, not a search for one answer, so every true table cell (or every successful expansion) contributes to the total rather than only the largest one.

## Pattern

Same interval / expand-around-center DP as Longest Palindromic Substring, with the output changed from "track the longest span found" to "tally every span that qualifies."

---

Canonical URL: https://www.marauderbot.com/questions/palindromic-substrings
