Palindrome Partitioning — The Banner Cuts

Boss 7: The Banner Cuts

The dungeon's choices so far: items (in/out), candidates (which weight), seats (who sits), tiles (which neighbor). This boss's choices are positions in a string, where to cut, and it introduces the pattern for every "split this sequence into valid pieces" problem: word break, IP address restoration, expression parsing. Plus a cameo from the oldest weapon in the quest: the two-pointer mirror check from Dungeon 2's very first boss.

The story

The print shop's ribbon reads "aab". Wall display rules: cut it into contiguous pieces, every piece a palindrome, reads identically both directions.

Enumerate at the cutting table:

• First piece "a" (mirror test: single letter, trivially passes). Rest is "ab": first piece "a" ✓, rest "b" ✓ → [a, a, b]. Or first piece "ab" from that remainder, "ab" reversed is "ba", fails the mirror. No snip.
• First piece "aa" ✓. Rest is "b" ✓ → [aa, b].
• First piece "aab"? Reversed "baa". Fails. No snip.

Catalog: [["a","a","b"], ["aa","b"]]. Two displays.

The table method, stated once and precisely: snip a front piece only if it passes the mirror test, then solve the remaining ribbon by the same rule. When a line of cutting dead-ends, tape the last snip back (the un-choose, literally adhesive here) and try the next longer front piece. The mirror test is the guard: it doesn't just validate finished displays, it refuses to even make a doomed snip, Boss 2's pruning philosophy, wearing scissors.

The problem, dressed up properly

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.

LeetCode 131.

The naive attempt

A string of length n has n-1 gaps, each cut-or-not: 2ⁿ⁻¹ partitions. Generate them all, filter for all-palindrome pieces:

def partition(s):
    out = []
    for mask in range(1 << (len(s) - 1)):
        pieces = split_by_mask(s, mask)
        if all(p == p[::-1] for p in pieces):
            out.append(pieces)
    return out

The Boss 1 bitmask, resurrected, and the same disease as ever: "aab" has 4 partitions and 2 winners, tolerable, but a 16-letter ribbon has 32,768 partitions, and if its first two letters already can't form palindrome pieces any way, every one of those candidates gets built and checked anyway. The guard-at-the-snip version never builds a partition whose first piece already failed. Filtering validates corpses; guarding prevents births.

The weapon: guarded cuts, one prefix at a time

The recursion's state is one index, start: everything before it is already snipped into blessed pieces (sitting in path); everything from it onward is uncut ribbon.

def partition(s: str) -> list[list[str]]:
    out = []
    path = []
 
    def is_pal(lo, hi):                  # Dungeon 2, Boss 1, reporting for duty
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True
 
    def cut(start):
        if start == len(s):
            out.append(path[:])          # ribbon exhausted: one display
            return
        for end in range(start + 1, len(s) + 1):
            if not is_pal(start, end - 1):
                continue                 # guard: doomed snip never made
            path.append(s[start:end])    # choose (the snip)
            cut(end)                     # explore (rest of the ribbon)
            path.pop()                   # un-choose (the tape)
    cut(0)
    return out

is_pal checks indices directly, no s[start:end][::-1] slicing, the two-pointer walk from the Museum Mirror boss, avoiding a copy per test. Small thing; on the pathological all-same-letter ribbon ("aaaa..."), where every substring passes and the tree is maximal, it's the difference between tight and bloated constants.

Watching it work

s = "aab":

cut(0)
├─ end=1: "a" ✓ snip → path [a]
│   cut(1)
│   ├─ end=2: "a" ✓ → [a,a]
│   │   cut(2)
│   │   └─ end=3: "b" ✓ → [a,a,b]  cut(3): DISPLAY ✓  tape b, tape a
│   └─ end=3: "ab"? mirror fails. no snip
│   tape a
├─ end=2: "aa" ✓ snip → [aa]
│   cut(2)
│   └─ end=3: "b" ✓ → [aa,b]  cut(3): DISPLAY ✓
└─ end=3: "aab"? mirror fails. no snip

catalog: [a,a,b] [aa,b] ✓

The two no snip lines are the guard earning its keep: the "ab"-and-onward universe and the "aab"-first universe were never entered, not explored-and-rejected, never entered.

Gotchas

1. Guarding after recursing. Appending the piece, recursing, and checking palindrome-ness at collection time is the naive filter wearing recursion's clothes. The guard's entire value is placement: before the snip, so failed pieces spawn no subtrees.

2. Off-by-one in the piece. s[start:end] with end exclusive, and the mirror test on (start, end-1) inclusive. Mixing the conventions checks the wrong window and blesses garbage or rejects gold. Pick exclusive-end everywhere and let range(start+1, len(s)+1) do the arithmetic.

3. Forgetting single letters pass. Every one-letter piece is a palindrome, which guarantees at least one partition always exists (all singles) and anchors the recursion. If your output is ever empty for a nonempty string, your mirror test rejects length-1 pieces.

4. Reversal slicing in the guard. s[start:end] == s[start:end][::-1] is correct and allocates two strings per test, called exponentially often. Index walking allocates none. In interviews either passes; knowing why you chose is the difference that gets noticed.

Complexity

Worst case (all same letter): every gap is a free choice, O(n · 2ⁿ) partitions generated and copied. The guard collapses realistic inputs far below it; the DP table trims guard costs to O(1) each.

Space: O(n) for path and stack, output aside.

Boss down. XP gained.

Two displays go to the director: three small tiles, or the bold AA beside a lone B. She picks the second, mutters "negative space", and the shop bills for both enumerations.

What you walked away with:

• Choices as cut positions: the split-into-valid-pieces recursion, template for word break and IP restoration
• The guard placement law: validate before the snip, and doomed universes are never born
• Dungeon 2's two-pointer mirror check, still earning wages seven dungeons later
• The DP-table precompute as the standard follow-up, and a preview of dungeons ahead

Next up: Boss 8 — The Vanity Number. An old phone keypad, where 2 is ABC and 3 is DEF, and a business wants every word its number could spell. The gentlest boss of the dungeon's back half: a pure Cartesian product, no pruning, no duplicates, just clean fan-out, and a look at why its tree is wider but shallower than everything before it.