1225. The Smallest Palindrome the Pattern Could Be

A pattern is made of the letters a, b, c and the wildcard ?. Replace every ? with one of the three letters so that the result reads the same forwards and backwards. Report the lexicographically smallest such result, or none if there is none.

a?c?a -> aacaa ?b? -> aba ab -> none

## What most people try first

Try all three letters at every wildcard, over all 3^q combinations, keeping the smallest palindrome. At 20 wildcards that is 3.5 billion combinations.

## The constraint, which pairs the positions up

Position i must equal position n - 1 - i. That links the positions into mirror pairs, each independent of every other pair, which is the whole structure of the problem:

• both fixed and equal: nothing to decide
• both fixed and different: no palindrome exists at all, answer none
• one fixed: the other is forced to match it
• both wildcards: free, so take the smallest letter, a
• the middle position of an odd-length pattern pairs with itself, so a wildcard
• there becomes a and a fixed letter there is always fine

## Why that gives the smallest

The pairs are independent, so the smallest palindrome is obtained by making each pair as small as it can be, and the earlier position of a pair is the one that counts for lexicographic order. A free pair can be anything, so a is right. A pair with one fixed letter has no choice. So there is nothing to search and the answer is a single pass.

The reference searches anyway, because the question is the smallest completion and a search that fills the positions left to right with the letters in increasing order produces it without needing the argument above. That makes the search the honest reference and the pair rule the independent check, which is how the expected outputs here were verified.

## Why the reference does not recurse

The search is one decision per position and the input can be 1200 characters long, so a recursion goes 1200 frames deep. Python's default recursion limit is 1000, and raising it does not raise the C stack that CPython actually uses, so a recursive reference crashes here. It is not only Python: a frame holding a few locals is tens of bytes, and at tens of thousands of positions the default thread stack in Java and the main stack in C run out too.

So the reference carries the stack itself. The only thing a recursive frame holds that a loop would lose is WHICH OPTION the frame was about to try next, so that is what the explicit stack stores:

``` nxt[i] = index of the next option to try at position i

i = 0; nxt[0] = 0 while i >= 0: if i == n: a complete string if accepted: answer it and stop i = i - 1 otherwise go back continue if nxt[i] has run past the options at i: i = i - 1 this position is exhausted, go back continue take option nxt[i] and increment nxt[i] <- this is the resume point if the option is refused: continue stay at i, try the next one record it; nxt[i+1] = 0; i = i + 1 descend ```

Three details make or break it. nxt[i] is incremented BEFORE the descent, so coming back to position i continues from the next option rather than repeating the one that just failed, which would loop forever. nxt[i+1] is reset to 0 on every descent, not once at the start, because position i+1 may be entered many times and each entry must start from its first option. And going back is i = i - 1 with no undo of out[i], because out[i] is overwritten before it is ever read again; the carried state lives in stv[i], indexed by position, so it unwinds for free.

In this problem the state carried per position is nothing at all: the constraint is between position i and position n - 1 - i, and when the search reaches i past the middle, position n - 1 - i is already settled and is read straight out of the answer being built.

## The settled boundaries

A single character is its own palindrome. A pattern of all wildcards becomes all as. Two different fixed letters at a mirror pair give none. All three are tested.

## Cost

O(n), one pass, with at most three options tried per position and no step ever undone once the mirror is consulted.

Constraints - `1 ≤ length of the pattern ≤ 1200` - every character is `a`, `b`, `c` or `?`