Why are there 2n − 1 centres?

An odd-length palindrome is centred on a character (n choices) and an even-length one on the gap between two characters (n − 1 choices). Together that is 2n − 1 centres, and every palindrome has exactly one.

Is expand around centre better than dynamic programming here?

Both take O(n²) time. Expanding around centres uses O(1) extra space, while the DP table dp[i][j] (is s[i..j] a palindrome?) uses O(n²). Manacher's algorithm counts them in O(n), but is rarely expected in interviews.

Do repeated substrings count more than once?

Yes. Substrings with different start or end positions count separately, so "aaa" has six: three "a", two "aa" and one "aaa".

Palindromic Substrings

Count every palindromic substring of a string by expanding two pointers outward from each of its 2n − 1 centres.

MediumSolve on LeetCode

Problem Understanding

Palindromic Substrings: given a string s, return how many of its substrings are palindromes. Substrings at different positions count separately, even if they are equal.

Examples: "abc" returns 3 (a, b, c). "aaa" returns 6 (a, a, a, aa, aa, aaa).

Attempt 1: Check Every Substring

There are about n²/2 substrings, and checking each one takes up to n steps: O(n³) time. Most of that work is repeated: checking s[1..5] re-checks s[2..4], which was already known to be a palindrome or not.

The Intuition: Grow Palindromes From Their Centres

A palindrome stays a palindrome when you peel one character off each end, so every palindrome can be grown outward from its centre. Turn that around:

Visit each of the 2n − 1 centres: every character (odd lengths) and every gap between two characters (even lengths).
Put lo and hi on the centre and step outward while s[lo] == s[hi].
Each successful step is one more palindrome: count it.

This is the same walk as Longest Palindromic Substring, counting every palindrome instead of keeping only the longest.

Interactive Walkthrough

The centres are visited in order, alternating character and gap. The palindrome grown so far is filled, lo and hi mark the next comparison, and every palindrome counted is listed beside the figure.

Dry Run Table

Input: s = "aaa"

Centre	Start	Palindromes found	Count
0	char 0	`a`	1
1	gap 0-1	`aa`	2
2	char 1	`a`, `aaa`	4
3	gap 1-2	`aa`	5
4	char 2	`a`	6

The answer is 6.

The Solution Template

Expand around each of the 2n − 1 centres and count every match.

Palindromic Substrings Code

1var countSubstrings = function(s) {
2    let count = 0;
3    const n = s.length;
4    for (let center = 0; center < 2 * n - 1; center++) {
5        let lo = Math.floor(center / 2), hi = lo + (center % 2);
6        while (lo >= 0 && hi < n && s[lo] === s[hi]) {
7            count++;
8            lo--;
9            hi++;
10        }
11    }
12    return count;
13};

Edge Cases & Common Mistakes

Forgetting even-length palindromes: checking only character centres misses "bb" in "abba" and returns 5 instead of 6.
One character: a single centre and one palindrome; the answer is 1.
All characters equal: every substring is a palindrome, so the count is n(n + 1) / 2, the worst case for time.
Counting distinct strings instead of positions: the problem counts positions, so equal substrings each count.

Summary

Every palindrome has one centre, so expanding two pointers from all 2n − 1 centres meets each palindrome exactly once. Count each match: O(n²) time, O(1) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Longest Palindromic Substring

Encode and Decode Strings