Palindromic Substrings
Count how many contiguous substrings of s are palindromes, counting substrings at different positions separately.
Open on LeetCode ↗Intuition
This is the same centre expansion as the longest-palindrome problem, and it carries the same even-length blind spot — but here the bug is far nastier, because it fails silently. Forget the gap centres on 'abba' and you get 4 instead of 6: no crash, no empty result, just a plausible-looking number that happens to be wrong, and nothing in the output tells you so. So sweep all 2n-1 centres. The second insight is about where the counting happens. Do not expand fully and then add one — every single successful expansion step is itself a distinct palindromic substring. From the centre of 'aaa', you match at width 1 and again at width 3, and both are real answers, so that one centre contributes 2. Increment inside the while loop, not after it. The invariant that makes this exact rather than approximate is that every palindromic substring has exactly one centre, so no substring is ever counted twice and none is missed.
The same 2n - 1 centres as the longest-palindrome problem, but counting instead of measuring. Each successful expansion step is a distinct palindrome, so incrementing inside the while loop counts them all with no extra bookkeeping.
Approach
Sweep both centre types
For every index i, expand once from (i, i) for odd-length palindromes and once from (i, i + 1) for even-length ones. That is 2n-1 centres in total. Unlike the longest-substring version, where a missed even palindrome sometimes still leaves the right answer because an odd one happens to be longer, here every missed centre subtracts directly from the count.
Count each successful expansion, not each centre
Inside the while loop, increment the total on every iteration before widening. Each iteration corresponds to one confirmed palindrome s[l:r+1], and a centre that expands three times has produced three distinct palindromic substrings of increasing width. Counting once per centre would collapse them all into one and undercount massively on repetitive strings.
Rely on the one-centre-per-palindrome bijection
Every palindrome has a unique centre: the middle character if its length is odd, the middle gap if even. That makes the map from palindromes to (centre, width) pairs a bijection, so summing the expansion counts over all centres counts every palindromic substring exactly once. No deduplication set is needed, which is what keeps the space at O(1).
Solution & live demo
Common pitfalls
Counting once per centre
while ...: l -= 1; r += 1 total += 1
while ...:
total += 1
l -= 1; r += 1A centre that expands three times contains three distinct palindromes, not one. The increment belongs inside the loop, where each iteration confirms one more.
Generating and testing every substring
for i in range(n):
for j in range(i, n):
if s[i:j+1] == s[i:j+1][::-1]: total += 1for l, r in ((i, i), (i, i + 1)):
That's O(n³) — the slicing and reversal cost O(n) per pair. Expansion reuses the work of the smaller palindrome inside each larger one, dropping it to O(n²).
Deduplicating identical substrings
seen = set() ... seen.add(s[l:r+1])
total += 1
The problem counts palindromic substrings by position, so the two "a"s in "aaa" are separate answers. Deduplicating by content undercounts every input with repeats.
Edge cases
Every expansion succeeds exactly once at width 1 and every gap fails, giving n = 3 — each single character is itself a palindrome.
The maximum case: every centre expands as far as the bounds allow, giving 6 = n*(n+1)/2.
Answer 6, of which the gap centres contribute the 'bb' and 'abba' that a character-only sweep would silently drop.
One odd centre expands once, one gap centre does not exist, so the count is 1.