Suppose $A$ is a finite alphabet. Let's call a word $w \in A^*$ $n$ -universal iff it contains every word from $A^n$ as a subword. What is the minimal possible length of an $n$-universal word over $A$? $|A| = m$.
It is definitely $\geq m^n + n - 1$ , because a word of length $m \geq n$ has $m - n + 1$ subwords of length $n$.
I think, that $|A|^n + n - 1$ is quite likely to be the exact answer, but do not know how to prove it.
It holds, however, for the following particular cases:
$m = 1$: $a^n$
$n = 2, m = 2$: $abbaa$
$n = 3, m = 2$: $abbbaaabab$
$n = 2, m = 3$: $ccacaabbcba$
