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?


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.