LeetCode #647 Medium

Palindromic Substrings

Count how many contiguous substrings of s are palindromes, counting substrings at different positions separately.

stringtwo pointersexpand around centrecounting

02

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.

03

Approach

1

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.

2

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.

3

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).

04

Solution & live demo

python

▶1class Solution:
▶2    def countSubstrings(self, s: str) -> int:
▶3        total = 0
▶4        for i in range(len(s)):
▶5            for l, r in ((i, i), (i, i + 1)):        # 2n-1 centres
▶6                while l >= 0 and r < len(s) and s[l] == s[r]:
▶7                    total += 1                       # each match IS a palindrome
▶8                    l -= 1
▶9                    r += 1
▶10        return total

05

Edge cases

All distinct characters, s = 'abc'

Every expansion succeeds exactly once at width 1 and every gap fails, giving n = 3 — each single character is itself a palindrome.

All identical, s = 'aaa'

The maximum case: every centre expands as far as the bounds allow, giving 6 = n*(n+1)/2.

Pure even palindrome, s = 'abba'

Answer 6, of which the gap centres contribute the 'bb' and 'abba' that a character-only sweep would silently drop.

Single character, s = 'a'

One odd centre expands once, one gap centre does not exist, so the count is 1.

06

Complexity

Time

O(n^2)

Space

O(1)

The quadratic worst case is real and reached by a string of identical characters, where every centre expands the full way.