Skibidi String (Editorial)

The problem can be shortened into , Given a binary string $t$ of length n-2 , Construct the lexicographically smallest string $s$ such that every window s_is_{i+1}s_{i+2} has f(s_is_{i+1}s_{i+2}) \bmod 2=t_i.

First let's understand $f$ on a string of length $3$ , there are only three shapes : all equal ($\mathtt{aaa}$) gives f=3 , exactly two equal (\mathtt{aab},\mathtt{aba},\mathtt{abb}) gives f=5 and all distinct ($\mathtt{abc}$) gives f=6 , Therefore t_i=0 exactly when s_i,s_{i+1},s_{i+2} are pairwise distinct , and t_i=1 exactly when the window has a repeated letter.

So only equalities between letters matter , and a window never needs more than $3$ distinct letters , which means the alphabet \{\mathtt{a},\mathtt{b},\mathtt{c}\} is enough , We precompute all $27$ windows over \{\mathtt{a},\mathtt{b},\mathtt{c}\} grouped by f \bmod 2 in lexicographic order.

Now we build $s$ greedily from left to right , each time taking the smallest letter that keeps the current window correct , However plain greedy fails : for t=\mathtt{10} the smallest first window is $\mathtt{aaa}$ , but then $\mathtt{aa}?$ can never be all distinct , The future can get stuck only when t_{i+1}=0 while s_{i+1}=s_{i+2} , since once s_{i+1}\neq s_{i+2} there is always a third letter in \{\mathtt{a},\mathtt{b},\mathtt{c}\} completing a distinct window , and a window with t=1 can always be completed by repeating a letter , Therefore greedy with the one-step lookahead

never gets stuck , and since every choice is the smallest letter that still leaves a valid completion , the resulting string is the lexicographically smallest.

Complexity O(27n)=O(n).

from collections import defaultdict as dd 
get=dd(list)

def f(s):
    st=set()
    for i in range(len(s)):
        for j in range(i,len(s)):
            st.add(s[i:j+1])
    return len(st)

for a in range(97,100):
    for b in range(97,100):
        for c in range(97,100):
            s=chr(a)+chr(b)+chr(c)
            get[f(s)%2].append(s)

def ok(j,i,t):
    return i+1>=len(t) or t[i+1]=='1' or j[1]!=j[2]

def solve():
    n=int(input())
    t=input()
    a=[j for j in get[int(t[0])] if ok(j,0,t)][0]
    for i in range(1,n-2):
        for j in get[int(t[i])]:
            if(a[-2]==j[0] and a[-1]==j[1] and ok(j,i,t)):
                a+=j[2]

                break
    print(a)

for _ in range(int(input())):
    solve()