Palindromic Substrings — Expand Around Center vs 2D DP

Problem Statement#

Given a string s, return the total number of palindromic substrings it contains. Substrings with different start or end indices count as different palindromes even if they look identical.

Example: s = "aaa" returns 6. The palindromes are "a", "a", "a", "aa", "aa", and "aaa". Notice that "a" is counted three times because it occurs at three different positions.

Example: s = "abc" returns 3 — only the single characters are palindromes.

Constraints: 1 is less than or equal to s.length is less than or equal to 1000, lowercase English letters. The size is small enough for O(n^2) but not for O(n^3) brute force.

Why This Problem Matters#

Palindromic Substrings is the "Hello World" of string DP. Amazon, Microsoft, Meta, and Bloomberg ask it (or its sibling Longest Palindromic Substring) constantly because it tests three skills at once: recognizing palindrome symmetry, choosing between bottom-up tabulation and the smarter expand-around-center pattern, and reasoning about whether the constant-factor space optimization is worth the slight code-complexity bump.

A strong candidate explains both approaches and picks expand-around-center. A weaker candidate jumps to the 2D DP table and never reaches the O(1) memory version. This blog teaches both so you can defend your choice.

The Core Insight (Recurrence)#

A substring s[i..j] is a palindrome if and only if s[i] == s[j] and the inner substring s[i+1..j-1] is also a palindrome. That is the natural 2D DP recurrence:

• dp[i][j] = true when i == j (single character).
• dp[i][i+1] = (s[i] == s[i+1]) (two-character base case).
• dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1] for length at least 3.

We count every cell that is true. This gives O(n^2) time and O(n^2) space.

The expand-around-center reformulation observes that every palindrome has a center: either a single character (odd length) or a pair of adjacent characters (even length). There are exactly 2n - 1 centers. For each center we extend two pointers outward while characters match. Each extension corresponds to one true DP cell, so we count the same palindromes without storing the table — O(1) extra space.

Building the DP Solution (Recursion to Memo to Tabulation)#

Top-down: isPalin(i, j) recurses on (i+1, j-1) with memoization. That gives the same O(n^2) time but stack-heavy recursion. Tabulation iterates by substring length (length 1, then 2, then 3, ...) so that dp[i+1][j-1] is already computed when we reach dp[i][j]. This length-first ordering is the same trick used in Longest Palindromic Subsequence and Matrix Chain Multiplication — internalize it.

The expand-around-center version is essentially "compute the DP cells in the order their centers reveal them." It is mathematically the same recurrence with a smarter traversal.

Visual Dry Run (DP Table Trace)#

Take s = "aaab" and trace the 2D dp[i][j] table (1 means palindrome, 0 means not, dash means out of range).

     j=0  j=1  j=2  j=3
i=0   1    1    1    0
i=1   -    1    1    0
i=2   -    -    1    0
i=3   -    -    -    1

Counting the 1s gives 7 palindromic substrings: three single as, one b, two "aa"s, and one "aaa". Expand-around-center reaches the same 7 by visiting centers 0, 0.5, 1, 1.5, 2, 2.5, 3 and counting valid expansions: 1 + 1 + 2 + 1 + 2 + 0 + 1 = 7 (the half-integer centers are even-length expansions).

Optimized Solution — Space-Optimized Python and JavaScript#

Python#

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
 
        def expand(left: int, right: int) -> int:
            found = 0
            while left >= 0 and right < n and s[left] == s[right]:
                found += 1
                left -= 1
                right += 1
            return found
 
        for i in range(n):
            count += expand(i, i)        # odd-length palindromes
            count += expand(i, i + 1)    # even-length palindromes
        return count

JavaScript#

var countSubstrings = function (s) {
  const n = s.length;
  let count = 0;
  const expand = (left, right) => {
    let found = 0;
    while (left >= 0 && right < n && s[left] === s[right]) {
      found += 1;
      left -= 1;
      right += 1;
    }
    return found;
  };
  for (let i = 0; i < n; i += 1) {
    count += expand(i, i);
    count += expand(i, i + 1);
  }
  return count;
};

Complexity Analysis#

• Time: O(n^2). Each of the 2n - 1 centers can expand up to n/2 steps, giving an n^2 bound.
• Space: O(1) for expand-around-center, O(n^2) for the tabulation DP. Memoization sits in between with O(n^2) memory and recursion stack overhead.
• Manacher's algorithm runs in O(n) but is rarely accepted in interviews unless explicitly asked — the constant factor and code complexity are not worth the memorization cost.

Common Mistakes#

• Forgetting even-length centers. Calling expand(i, i) only finds odd palindromes; you must also call expand(i, i + 1).
• Off-by-one in the boundary check. Use left >= 0 AND right less than n strictly. A common bug is comparing right is less than or equal to n and indexing out of bounds.
• Counting palindromes by content rather than position. The problem counts each occurrence. Do not deduplicate.
• Building a set of strings. That changes the answer for "aaa" from 6 to 3 — a classic interview trap.
• Confusing this with Longest Palindromic Substring. Same algorithm shape, but here we count, there we track max length and indices.

Interview Tips#

• Lead with the recurrence: "A substring is a palindrome if its outer characters match and its inner substring is also a palindrome." That sentence earns DP credit immediately.
• Then say: "I will implement the smarter expand-around-center variant because it has the same O(n^2) time but only O(1) memory." Interviewers love that tradeoff.
• If asked for O(n), mention Manacher's algorithm but only sketch it; do not try to code it under pressure.
• Discuss test cases: empty string, single character, all identical characters, no palindromes, strings of length 1000.

Follow-up Questions#

• Return the longest palindromic substring instead of counting them. Track the best (start, length) inside expand.
• Return the unique palindromic substrings as strings. Use a set keyed on the substring slice.
• Count palindromic subsequences (not contiguous). Different problem — that is interval DP with three branches.
• Solve in O(n) time. That is Manacher's algorithm; mention it for completeness.

Key Takeaways#

• Palindromic Substrings is solved by a clean 2D DP recurrence on substring intervals, then optimized to expand-around-center for O(1) memory.
• The two flavors of centers — single character and adjacent pair — are mandatory; missing the even-length case is the most common interview bug.
• Time complexity is O(n^2) for both approaches; space is the differentiator and the reason expand-around-center wins.
• The same DP shape powers Longest Palindromic Substring, Longest Palindromic Subsequence, and many string-DP follow-ups.
• Always count by position, not by string identity, unless the prompt explicitly asks for unique palindromes.
• Mentioning Manacher's algorithm shows depth, but only commit to coding it if the interviewer asks.