I'm not familiar with this particular problem, but can ideas from De Bruijn Sequences be applied?

https://en.wikipedia.org/wiki/De_Bruijn_sequence