Palindromic Substrings — Solution

Problem

Given a string, count how many of its substrings are palindromes — sequences that read the same forwards and backwards. Every individual character counts as a palindrome on its own.

• Input: s = "aaa"
• Output: 6
• Explanation: The palindromic substrings are "a", "a", "a", "aa", "aa", and "aaa".

Counter-example: "abc" produces 3 — only the three single characters, since no multi-character substring reads the same in both directions.

Intuition

Every palindrome has a center: either a single character (odd length) or the gap between two adjacent characters (even length). If you stand at a center and expand outward one character at a time, every step where the left and right characters match reveals another palindrome. The key insight is that all valid expansions from a center form a chain — once a mismatch occurs, no further expansion from that center can be palindromic.

Approach 1 — Expand Around Center

For each of the 2n − 1 possible centers, expand outward while the flanking characters match. Each successful expansion contributes one palindrome to the count.

1. Iterate over every index as a potential center.
2. For odd-length palindromes, expand starting with both pointers at the same index.
3. For even-length palindromes, expand starting with the left pointer at the index and the right pointer one ahead.
4. In each expansion, advance inward-out while bounds hold and characters match, incrementing the count each step.
5. Return the total count.

1def countSubstrings(s: str) -> int:
2    count = 0
3
4    def expand_from_center(left: int, right: int) -> int:
5        palindromes = 0
6        while left >= 0 and right < len(s) and s[left] == s[right]:
7            palindromes += 1
8            left -= 1
9            right += 1
10        return palindromes
11
12    for center in range(len(s)):
13        count += expand_from_center(center, center)      # odd-length: single char center
14        count += expand_from_center(center, center + 1)  # even-length: gap between chars
15    return count

Time: O(n²) — at most n expansions per center, across 2n − 1 centers.
Space: O(1) — only two pointer variables per expansion; no auxiliary storage.

Approach 2 — Dynamic Programming

Build a 2-D boolean table where dp[start][end] is true when s[start..end] is a palindrome. Fill it by increasing substring length so that shorter results are always available when computing longer ones.

1. Create an n × n boolean table, initially all false.
2. Iterate length from 1 to n.
3. For each starting index, compute the ending index.
4. Mark dp[start][end] true when the outer characters match and the inner substring (already computed) is also a palindrome. Length 1 and 2 need no inner lookup.
5. Increment the count whenever a cell is marked true.

1def countSubstrings(s: str) -> int:
2    n = len(s)
3    count = 0
4    dp = [[False] * n for _ in range(n)]
5
6    for length in range(1, n + 1):
7        for start in range(n - length + 1):
8            end = start + length - 1
9            # length <= 2: no inner substring to check, outer match is sufficient
10            if s[start] == s[end] and (length <= 2 or dp[start + 1][end - 1]):
11                dp[start][end] = True
12                count += 1
13    return count

Time: O(n²) — filling every cell in the n × n table once.
Space: O(n²) — the DP table stores a boolean for every substring.

Complexity Summary

Common Mistakes

• Forgetting even-length palindromes — expanding only from a single center character finds odd-length palindromes like "aba" but misses "aa". A second expansion starting at (center, center + 1) is required.
• Checking characters before checking bounds — s[left] == s[right] before left >= 0 && right < n causes an index-out-of-bounds when the expansion reaches the string edge. Bounds must come first in the condition.
• Iterating DP by start index instead of by length — if you loop over start in the outer loop, dp[start + 1][end - 1] references a cell for a longer interval that hasn't been computed yet. The outer loop must be over length.
• Omitting the length ≤ 2 guard in DP — for a length-2 substring s[i..i+1], dp[i+1][i] is out-of-order and undefined. The condition length <= 2 short-circuits this lookup, treating a matching pair of adjacent characters as a base case.
• Returning a substring instead of a count — the problem asks how many palindromic substrings exist, not which one is longest. A common slip is returning max_length or the actual substring, especially after recently solving Longest Palindromic Substring.

Related Problems

• longest-palindromic-substring — identical technique, but tracks the longest palindrome found rather than counting all of them
• palindrome-partitioning — uses palindrome checking as a subroutine to split a string into all-palindrome parts via backtracking
• longest-palindromic-subsequence — palindrome DP on non-contiguous characters rather than substrings
• valid-palindrome — foundational palindrome check that underpins all palindrome problems
• valid-palindrome-ii — extends the two-pointer palindrome check to allow one character removal