1231. The Smallest String With No Two Neighbours Alike

A pattern is made of lowercase letters and the wildcard ?. An alphabet size k is given, so the letters available are the first k of a, b, c, and so on, and every fixed letter in the pattern is inside that alphabet. Replace every ? with one of the k letters so that no two neighbouring characters are equal. Report the lexicographically smallest such string, or none if there is none.

a?a, k = 3 -> aba ??????, k = 2 -> ababab aa, k = 2 -> none ?, k = 1 -> a

## What most people try first

All k^q completions, keeping the smallest valid one. Six wildcards over three letters is 729 and the pattern can have 1200 of them.

## The constraint reaches one position

A character is constrained only by the one before it, so there is no running state at all beyond the string being built: refuse a letter equal to the previous character.

## Why that is enough, and the one place it is not

With k at least 3 the smallest legal letter at each position is always safe, because the only forbidden letter is the previous character, so at least two letters remain and one of them differs from whatever the NEXT fixed character turns out to be. So with three letters or more the search never backtracks and the answer is the greedy one.

With k = 2 the choice at a wildcard is forced the moment the previous character is known, so again nothing is undone, and the only way to fail is for the pattern itself to contain two equal neighbours.

With k = 1 the only legal string is a single character, since any two neighbours would be equal.

So this problem never backtracks, and saying so is more useful than pretending it might. What it does need is the explicit stack, for the same reason as the rest of the batch: one decision per position and up to 1200 positions.

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

## Why the first complete string is the smallest

Positions are filled left to right and the letters are tried in increasing order, so the first complete string differs from any other at a position where the other took a larger letter.

## The settled boundaries

k = 1 works only on a pattern of length 1. Two equal fixed neighbours give none whatever k is. A pattern of all wildcards with k at least 2 gives ababab.... All are tested.

## Cost

O(n * k) with no step undone, and O(n) output.

Constraints - `1 ≤ length of the pattern ≤ 1200` - `1 ≤ k ≤ 26` - every fixed letter is among the first `k` lowercase letters