Palindromic Substrings

Difficulty: Medium Source: NeetCode

Problem

Given a string s, return the number of palindromic substrings in it. A substring is a contiguous sequence of characters within the string.

Example 1: Input: s = "abc" Output: 3 (Palindromes: “a”, “b”, “c”)

Example 2: Input: s = "aaa" Output: 6 (Palindromes: “a”, “a”, “a”, “aa”, “aa”, “aaa”)

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters

Prerequisites

Before attempting this problem, you should be comfortable with:

• Longest Palindromic Substring — the expand-around-center technique
• Palindrome Counting — understanding that each expansion step adds a new palindrome

1. Brute Force

Intuition

Check every possible substring to see if it’s a palindrome. For each valid palindrome, increment the count. This is O(n³) due to the nested loops plus the palindrome check, but simple to reason about.

Algorithm

1. For every pair (i, j), check if s[i:j+1] is a palindrome.
2. Increment count if it is.
3. Return the total count.

Solution

def countSubstrings_brute(s):
    n = len(s)
    count = 0

    for i in range(n):
        for j in range(i, n):
            sub = s[i:j + 1]
            if sub == sub[::-1]:
                count += 1

    return count


print(countSubstrings_brute("abc"))  # 3
print(countSubstrings_brute("aaa"))  # 6
print(countSubstrings_brute("a"))    # 1
print(countSubstrings_brute("aa"))   # 3

Complexity

• Time: O(n³) — n² substrings × O(n) palindrome check
• Space: O(n) — substring allocation

2. Expand Around Center

Intuition

Just like the Longest Palindromic Substring problem, expand from every center. But instead of tracking the longest, increment the count for each successful expansion step. Each step outward that still forms a palindrome is one more palindromic substring.

There are 2n - 1 centers: n single characters (odd palindromes) and n-1 gaps (even palindromes). Each character starts as a palindrome of length 1, so start the count at n and add extras as you expand.

Algorithm

1. For each center (char and gap):
   • Expand outward. Each successful expansion = +1 to count.
   • The center itself (single char) counts as 1, so initialize count to 0 and increment on each valid window including the center.
2. Return total count.

Solution

def countSubstrings(s):
    n = len(s)
    count = 0

    def expand(left, right):
        nonlocal count
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(n):
        expand(i, i)      # odd-length palindromes
        expand(i, i + 1)  # even-length palindromes

    return count


print(countSubstrings("abc"))  # 3
print(countSubstrings("aaa"))  # 6
print(countSubstrings("a"))    # 1
print(countSubstrings("aa"))   # 3
print(countSubstrings("aba"))  # 4  ("a","b","a","aba")

Complexity

• Time: O(n²) — n centers, each expanding up to O(n)
• Space: O(1) — just a counter and indices

Common Pitfalls

Not counting the center itself. When expand(i, i) is called, the first iteration where left == right == i and s[i] == s[i] is always true — that’s the single character palindrome. Make sure the increment happens inside the while loop so it counts this base case.

Missing even-length palindromes. Don’t forget expand(i, i+1) for each i. A string like “aaa” has three “aa” palindromes, which only get counted with even-center expansion.

Treating this as “count distinct palindromes”. The problem counts by occurrence, not uniqueness. In “aaa”, the string “aa” appears twice and both count separately.