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

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:

// Java: Expand Around Center
total = 0;
for (int c = 0; c < 2 * s.length() - 1; c++) {
    int left = c / 2;
    int right = left + c % 2;
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        total++;
        left--;
        right++;
    }
}
return total;

🧠 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.