Problem 70: Dense Binary Words
A word is called dense if it has the largest number
of (distinct) factors among words of the same length on the same alphabet.
Over an alphabet with at least three letters, generating dense words for any
given length is solved by the generation of perfect words (see
Problem 69).
But the solution does not apply to binary words and the
present problem shows how to deal efficiently with this case.
Show how to construct in $O(N)$ time a dense binary word of any given
length $N$.
Consider Hamiltonian and Eulerian cycles in de Bruijn automata.
References
D. Repke and W. Rytter. On semi-perfect de Bruijn words. Theor.
Comput. Sci., 720:55-63, 2018.
J. Shallit. On the maximum number of distinct factors of a binary string.
Graphs and Combinatorics, 9(2-4):197-200, 1993.