DSAPrep
Medium1-D DP

Palindromic Substrings

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Example 1

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.
View original on LeetCode ↗

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":

a
0
a
1
a
2
count = 1
1 / 6
resultcurrent

Odd center i=0: single char "a" is a palindrome. count = 1.

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.