Minimum number of nucleotides to force duplicate substring

Question

There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T.

Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of nucleotides I would have to encounter before I'm pigeonholed into seeing a duplicate substring of length 3.

Observe that a string of 4 nucleotides could produce a duplicate substring of length 3 (although I'm not forced into a pigeonhole since there are other strings of length 4 that don't produce a duplicate).

AAAA

Substrings [0-3) and [1-4) are both "AAA", so a duplicate occurrence of a length 3 substring has appeared.

I originally tried concatenating together every combination of 3 nucleotides.

[AAA][CAA][GAA][TAA][ACA][CCA]
AAACAAGAATAAACACCA...

But this algorithm produces a duplicate rather quickly: substrings [0-3) and [10-13).

I know there are 4^3 = 64 different substrings of length 3, so an upper bound to force pigeonholing is a string of length (64 * 3) + 1 = 195 -> one of the 64 substrings must appear twice. I've convinced myself that this can be bounded tighter to length 67 since this could contain 64 different substrings that start at indexes 0-63 and one duplicate that starts at 64. The interleaving of the substrings with each other is what makes them hard to analyze. How much tighter can this bound go, and what is an algorithm for producing a sequence that forces a pigeonhole?

Answer 1

The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is repeated.

The latter can be obtained from a de Bruijn sequence with $n=3$ and $k=4$. The length of this sequence is $k^n=64$ symbols. A de Bruijn sequence is a cyclic string such that every possible length-$n$ string occurs exactly once as a substring of it. It is known that a de Bruijn sequence of length $k^n$ exists. If we take the de Bruijn sequence $x_1 x_2 \cdots x_{64}$, then $x_1 x_2 \cdots x_{64} x_1 x_2$ is an ordinary string where every possible length-3 string occurs exactly once as a substring. In particular, no length-3 substring of $x_1 x_2 \cdots x_{64} x_1 x_2$ is repeated. There are also standard algorithms to find such a string.