🗓️ Day 32: Palindromic Substrings with Center Expansion

🧠 Concept Deep Dive

Another elegant way to count palindromic substrings — without the full DP table — is center expansion. Every palindrome is centered around a single character (odd length) or between two characters (even length).

Instead of checking all substrings, we just expand around each possible center.

There are 2n - 1 possible centers for a string of length n.

🎯 Visual Intuition

For s = "aba":

Centers:\ a (index 0)\ b (index 1)\ a (index 2)\ Between a-b\ Between b-a

Each of these centers is expanded outward as long as the characters match.

aba
 ^
 ^ ^

aba
 ^^^ ← expands out

aba
^   ^ ← also expands

🛠️ Key Patterns

🔍 Expand Around Center

function countSubstrings(s: string): number {
  let count = 0;

  for (let center = 0; center < 2 * s.length - 1; center++) {
    let left = Math.floor(center / 2);
    let right = left + (center % 2);

    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++;
      left--;
      right++;
    }
  }

  return count;
}

📘 Example

Input: "abcba"\ Output: 7

Palindromes:\ "a", "b", "c", "b", "a", "bcb", "abcba"

Same result as Day 31 — but no DP table!

🧪 Homework

Implement countSubstrings(s: string) using center expansion
Modify it to print each palindromic substring found
Compare runtime vs. DP solution from Day 31 on larger inputs

🧠 Big-O Cheat Sheet

Time: O(n^2) — worst case we expand n times for 2n-1 centers
Space: O(1) — constant space!

🔮 Up Next

▶️ Day 33: Longest Palindromic Substring