647 - Palindromic Substrings

Difficulty: Medium | Pattern: Expand Around Center | Company tags: Google, Amazon, Facebook, LinkedIn

Problem Statement

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 substrings: "a", "b", "c"

Example 2:

Input: s = "aaa"
Output: 6
Explanation: 6 palindromic substrings: "a", "a", "a", "aa", "aa", "aaa"

Constraints: 1 <= s.length <= 1000; s consists of lowercase English letters.

Approach: Expand Around Center — O(n²) time, O(1) space

Key insight: Same as LeetCode 5 (Longest Palindromic Substring). Every palindrome has a center. Expand around each possible center (each character for odd-length, each gap for even-length) and count how many palindromes each center generates.

def countSubstrings(s: str) -> int:
    count = 0
    n = len(s)
    
    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 centered at i
        expand(i, i+1)  # even-length palindromes centered between i and i+1
    
    return count

Dry Run

s = "aaa"

Center	Expansion type	Palindromes found
i=0, odd	(0,0): "a" → count=1; expand (-1,1): out of bounds	1
i=0, even	(0,1): s[0]='a'==s[1]='a' → "aa" count=2; expand (-1,2): out of bounds	1
i=1, odd	(1,1): "a" count=3; expand(0,2): s[0]='a'==s[2]='a' → "aaa" count=4; expand(-1,3): out of bounds	2
i=1, even	(1,2): s[1]='a'==s[2]='a' → "aa" count=5; expand(0,3): out of bounds	1
i=2, odd	(2,2): "a" count=6; expand(1,3): out of bounds	1
i=2, even	(2,3): out of bounds	0

Total: 6 ✓

Comparison with LeetCode 5

Problem	Goal	Key difference
5 - Longest Palindromic Substring	Find the longest palindrome	Track start/end of longest
647 - Palindromic Substrings	Count all palindromes	Increment count on each expansion

The expand-around-center logic is identical — only what you track changes.

Alternative: DP — O(n²) time, O(n²) space

def countSubstrings(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    
    for length in range(1, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and (length <= 2 or dp[i+1][j-1]):
                dp[i][j] = True
                count += 1
    
    return count

Complexity

Approach	Time	Space
Expand around center	O(n²)	O(1)
DP	O(n²)	O(n²)

Expand around center is preferred for its O(1) space.