Avoid 01 and 12 — Solution & Editorial

Back to the Problem

Build the Aho–Corasick automaton of the forbidden set; delete terminal (matched) states. The transfer matrix over surviving states, raised to the N-th power, counts safe strings.

Complexity: O(states³ log N)

Watch out: A state is dead if it or any of its failure-link ancestors is terminal — propagate the terminal flag along fail links.