Problem statement

https://binarysearch.com/problems/Smallest-Number-With-No-Adjacent-Duplicates/

Solution

Go symbol by symbol from left to right and choose the smallest possible.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        s = list(s)
        for i in range(n):
            if s[i] != "?":
                continue
            else:
                cands = set(["1", "2", "3"])
                if i: cands.remove(s[i - 1])
                if i + 1 < n: cands.discard(s[i + 1])
                s[i] = min(cands)

        return "".join(x for x in s)