What is the minimum longest repeated substring of a binary string of size n?

Question

The longest repeated substring of 0111011 is 011 for example. My question is given the size of a binary string, what is the shortest this longest repeated substring can be.

I have computed values for some small values of n:

n=1 : 0 (no repeated substring)
n=2 : 0
n=3 : 1  (010)
n=4 : 1  (0110)
n=5 : 1  (01100)
n=6 : 2  (010110)
n=7 : 2  (0101100)
...

What is the pattern here?

Answer 1

The de Bruijn sequences are extremal for the property you have in mind. For a $k$-element alphabet, these are cyclic sequences of length $k^n$ such that, as you slide an $n$-long window along the sequence, you see each one of the $k^n$ $n$-long strings exactly once -- therefore the longest repeated substring has length $n-1$. (For a non-cyclic sequence, you just wrap around to the beginning a little, so you get ordinary sequences of length $k^n+n-1$ having every possible $n$-long string exactly once.)