The O(n) Club: Palindromic Substrings: The Hunt That Expands Out (Not Downward Spiral)

⚡ TL;DR

Counting all contiguous palindromic substrings? Stop crying in your triple-for-loops. Treat every letter—and every gap between letters—as a potential “mirror center” and just expand both ways. It’s O(n²) time, no memory gym required.

Here’s the brain-teaser in code:

🧠 How Devs Usually Mess This Up

Classic panic move: brute-force all substrings, then ask if each one is a palindrome. Welcome to O(n³): where your runtime is matched only by your despair. Another favorite: Only check palindromes of odd length (because who needs symmetry, right?) Or get lost chasing the longest palindrome instead. Wrong game, boss.

🔍 What’s Actually Going On

Picture every single letter and every gap between letters as the epicenter of a tiny palindromic earthquake. From each center: stretch out left and right as long as the letters keep matching. Each successful stretch? That’s a palindromic substring. Example: for “ababa,” there are nine centers (five letters + four gaps). For each, you keep counting until the symmetry collapses. Visualize a Rorschach test, but with less psychology and more symmetry.

🛠️ PseudoCode

Loop over all possible centers (characters and gaps):
- Odd: centers at characters. Even: centers between characters.
For each center, set left/right pointers accordingly.
While left and right are within the string and match:
- Boom—a new palindrome. Add to your count.
- Expand out: left–, right++
Do this for every possible center. You’re done before your coffee cools.