Palindromic Substrings

This is the counting twin of Longest Palindromic Substring, and the same expand-around-center trick applies: every palindrome is centered on either a single character (odd length) or a gap between two characters (even length). Instead of tracking the longest one found, just count every successful expansion – each one is a distinct palindromic substring.

Brute Force

Time O(n³)Space O(1)

Check every substring directly and count the ones that are palindromes.

class Solution:
    def countSubstrings(self, s: str) -> int:
        def isPalindrome(sub: str) -> bool:
            return sub == sub[::-1]

        n = len(s)
        count = 0
        for i in range(n):
            for j in range(i, n):
                if isPalindrome(s[i:j + 1]):
                    count += 1
        return count

O(n²) substrings, each checked in O(n) → O(n³) time, O(1) extra space.

Expand Around Center

OptimalTime O(n²)Space O(1)

For each of the 2n - 1 centers, expand outward while characters keep matching, incrementing a counter on every successful match (each match is a new palindromic substring, since a wider match implies the narrower ones inside it were already counted at earlier expansion steps).

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expand(l: int, r: int) -> int:
            local_count = 0
            while l >= 0 and r < len(s) and s[l] == s[r]:
                local_count += 1
                l -= 1
                r += 1
            return local_count

        n = len(s)
        count = 0
        for i in range(n):
            count += expand(i, i)
            count += expand(i, i + 1)
        return count

Trace for s = "aaa":

Watch l and r grow outward from each center, the active center chip move along the 2n - 1 centers, and the count tick up once per matching width.

Centers

a·a·a·

odd center i=0match = "a"count = 1

1 / 6

currentseenresult

Odd center i=0: the single character a is a palindrome by itself. When l and r point at the same cell the match is free, so count grows by 1 with no comparison.

Each of the n centers can expand up to O(n) times → O(n²) time, O(1) space for the pointers and counter – matching the time of the O(n²) 2-D dp[i][j] table approach without needing O(n²) space to store it.

Palindromic Substrings

Brute Force

Expand Around Center

More 1-D DP practice