Palindromic Substrings

Given a string s, return the number of substrings within s that are palindromes.

A palindrome is a string that reads the same forward and backward.

"a", "b", "c".

"a", "a", "a", "aa", "aa", "aaa". Note that different substrings are counted as different palindromes even if the string contents are the same.

Approach

Count palindromes by expanding around every center. For each index, expand for odd and even centers and add how many valid palindromes are found.

Why It Works

Every palindromic substring is determined by a center. Expanding from all centers counts each palindrome exactly once, so the total count is correct.

Complexity

• Time: O(n^2)
• Space: O(1)

Reference Implementation (Python)

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

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