Palindromic Substrings

Problem

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.

Solution

Approach 1: Expand Around Center

The key insight is to expand around each possible center (single character for odd-length, between characters for even-length) and count palindromes.

Implementation

class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0

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

        for i in range(len(s)):
            # Odd length palindromes (center is single character)
            expand_around_center(i, i)
            # Even length palindromes (center is between characters)
            expand_around_center(i, i + 1)

        return count

Approach 2: Dynamic Programming

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0

        # Single characters are palindromes
        for i in range(n):
            dp[i][i] = True
            count += 1

        # Check two-character substrings
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                count += 1

        # Check longer substrings
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    count += 1

        return count

Approach 3: Expand Around Center (Cleaner)

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

        total = 0
        for i in range(len(s)):
            # Odd length
            total += count_palindromes(i, i)
            # Even length
            total += count_palindromes(i, i + 1)

        return total

Complexity Analysis

Expand Around Center:

Time Complexity: O(n²), where n is the length of string. For each of n centers, we expand up to O(n) times.
Space Complexity: O(1), only using constant space.

Dynamic Programming:

Time Complexity: O(n²), filling n² DP table.
Space Complexity: O(n²) for the DP table.

Key Insights

Two Types of Centers: Palindromes can have odd length (center is a character) or even length (center is between two characters).
Expand and Count: For each center, expand outward while characters match, counting each valid palindrome found.
All Single Characters: Every single character is a palindrome, contributing n to the count.
DP Relation: A substring s[i..j] is a palindrome if s[i] == s[j] and s[i+1..j-1] is a palindrome.
Space-Time Tradeoff: Expand around center uses O(1) space but same O(n²) time as DP, making it more efficient overall.
Count During Expansion: Each expansion step that finds matching characters adds one palindrome to the count.