Palindromic Substrings — The Mirror Tally

Boss 6: The Mirror Tally

Boss 5 built the expansion engine: 2n-1 centers, grow outward while the ends match. This boss doesn't touch the engine. It swaps the odometer. The question changes from "which mirror is longest?" to "how many mirrors are there?", and the only code change is what you do on each successful match: instead of comparing against a champion, you count. The real lesson is noticing when a solved problem's machinery transfers wholesale.

The story

The dealer stamped the plate's value and moved on. Her apprentice inherits the tedious part: the shop ledger must list every mirrored phrase on the plate, however short. Single letters count, they read the same both ways, trivially.

Today's plate reads aaa. Small plate, right?

plate: a a a

single letters:  "a", "a", "a"            → 3 entries
pairs:           "aa" (0-1), "aa" (1-2)   → 2 more
the whole plate: "aaa"                    → 1 more
ledger total: 6

Six entries from three letters. Note the two "aa" entries: same text, different positions on the plate, and the ledger logs positions, not spellings. The apprentice sighs, then remembers watching the dealer work: stand at a center, grow outward, stop at a mismatch. Every phrase the dealer's method ever touched was a mirror. So instead of remembering the longest one... just count every touch.

The problem, dressed up properly

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string, and substrings with the same characters but different start positions are counted separately.

LeetCode 647.

The naive attempt

Generate every substring, check each one:

def count_substrings(s):
    count = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i:j + 1]
            if sub == sub[::-1]:
                count += 1
    return count

O(n²) substrings times O(n) per check: O(n³), the same wall Boss 5's naive attempt hit. And the same waste: verifying "aaa" re-verifies the inner "a" you already trusted. When a check keeps re-earning knowledge it already had, the structure of the problem is telling you to grow answers from smaller ones instead.

The weapon: same engine, new odometer

Here's the observation that makes this boss a five-minute fight. During a Boss 5 expansion, every successful step is itself a complete palindrome. Expanding around center 1 of aaa first confirms a, then grows to confirm aaa. That's not one palindrome discovered, it's two. And since every palindrome has exactly one center, counting one tick per successful step at each of the 2n-1 centers counts every palindrome exactly once. No misses, no doubles.

def count_substrings(s: str) -> int:
    count = 0
 
    def expand(left: int, right: int) -> None:
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1                    # each match is one whole mirror
            left -= 1
            right += 1
 
    for center in range(len(s)):
        expand(center, center)            # odd-length mirrors
        expand(center, center + 1)        # even-length mirrors
    return count

Compare it line by line with Boss 5. The loop shape, the two calls per position, the boundary checks: identical. The champion-tracking is gone, a counter sits in its place. That's the whole diff.

Watching it work

aaa:

center 0 odd:   "a"                    +1   (tally 1)
gap 0-1 even:   "aa"                   +1   (tally 2)
center 1 odd:   "a", grow → "aaa"      +2   (tally 4)
gap 1-2 even:   "aa"                   +1   (tally 5)
center 2 odd:   "a"                    +1   (tally 6)
gap 2-3 even:   right edge, no room     0
total: 6 ✓

Each of the six palindromes got exactly one tick, at its own center, during its own expansion step. The two "aa" entries came from different gaps, positions counted separately, just as the ledger demands.

Gotchas

1. Counting per center instead of per step. Adding 1 after each expansion finishes counts 2n-1 at most, missing every nested mirror. The tick belongs inside the while loop, one per successful match.

2. Deduplicating by spelling. Storing found palindromes in a set collapses the two "aa" entries into one and returns 5 for aaa. Positions count, content doesn't. Plain integer counter, no set.

3. Forgetting the even centers, again. The Boss 5 classic returns for an encore. Odd-only expansion on aaa gives 4 instead of 6, quietly dropping every even-length mirror. Two calls per position, always.

4. Worrying about double counting. The step that stops people trusting this solution: could one palindrome be ticked at two different centers? No. A palindrome determines its center uniquely (midpoint of its span), so each is counted at exactly one center, exactly once. Say this in the interview, it's the correctness proof in one sentence.

Complexity

2n-1 centers, each expanding at most n/2 steps, with O(1) work per step.

Time: O(n²). Space: O(1).

Boss down. XP gained.

The apprentice closes the ledger: six mirrors on a three-letter plate, logged in one pass of the dealer's own technique, and the dealer never had to explain anything twice.

What you walked away with:

• Same engine, different odometer: max-tracking became counting, nothing else moved
• Every successful expansion step is a complete palindrome in its own right
• Each palindrome has exactly one center, so the count is exact, no dedup needed
• The reuse instinct sharpened: Boss 4 reused a whole algorithm, this boss reused a whole traversal

Next up: Boss 7 — The Numbers Station. A spy radio reads out a string of digits, and the question stops being about mirrors: how many different ways can the message decode? DP as a counter of possibilities returns.