CLR cover
Previous problem

Problem 70: Dense Binary Words

Next problem

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.