1226. The Smallest String With No Three Alike in a Row

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

aa?aa -> aabaa ?????? -> aabaab aaa -> none

## What most people try first

All 3^q combinations, keeping the smallest valid one. Six wildcards is 729 and twelve hundred is beyond counting.

The greedy instinct is to take the smallest letter that does not complete a triple, and here it is almost right and worth being precise about. Greedy looks only backwards, at the two characters before. It can therefore walk into a position whose fixed letter completes a triple with the two it just chose, and greedy cannot take them back.

## The constraint is local, which is what makes this cheap

A character is only ever constrained by the two before it. So the running state is just those two characters, which the search already has in the answer it is building. A step is refused exactly when the chosen letter equals both of them.

## Why the first complete string is the smallest

The positions are filled left to right and the letters are tried a, b, c, in increasing order. Any other valid completion differs from the first one found at some position where it took a larger letter, so the first one found is smaller.

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

The undo matters here in a way it did not in #1225: a step can be refused for a reason that only becomes visible later, when a fixed letter two positions on turns out to complete a triple, and then the loop goes back and tries the next letter at the earlier position. That is real backtracking, and it is why this problem is not a single forward pass.

## The settled boundaries

Three equal FIXED letters in a row can never be repaired, so the answer is none; that is tested. A pattern of all wildcards gives aabaabaab..., which is a wherever the previous two are not both a and b otherwise, and it is the smallest string with no triple. A pattern with no wildcards is itself if it has no triple.

## Cost

O(n) steps with at most three options each and a bounded amount of backtracking, since a refusal is always caused by a fixed letter within two positions.

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