Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, never repeats.

For example, with $n = 1$, I have a maximum length of $2$, obtained with $(0, 1)$ or $(1, 0)$.

For $n=2$ I think the maximum should be $5$, which I can obtain with the sequence $(0,0,1,1,0)$.

Similarly, I can get a length of at least $9$ for $n=3$ and $15$ for $n=4$ with the sequences $(0,0,0,1,0,1,1,0,1)$ and $(0,0,0,0,1,0,0,1,1,0,1,1,1,0,1)$ respectively.

Obviously I can write an exhaustive search with a number of operations proportional to $2^{f(n)}$, but this starts to be impractical already for $n=6$.

Any hint for reducing the time complexity? Is it possible in the first place?

  • $\begingroup$ This kinda looks like a de Bruijn sequence, maybe there is a similar construction method? $\endgroup$
    – Nathaniel
    Mar 5, 2022 at 15:09

1 Answer 1


I think that $f(n) = 2^n + n - 1$. To construct a word of length $f(n)$ with no repeated substring of length $n$, pick $\beta_n$ the $n$-th de Bruijn sequence over the alphabet $\{0, 1\}$ (of length $2^n$), and add the first $n-1$ letters of $\beta_n$ at the end.

Here's some examples:

  • for $n = 2$, pick $(0, 0, 1, 1, 0)$;
  • for $n = 3$, $(0,0,0,1,0,1,1,1,0,0)$ of length $10$ (and not $9$ as you suggested);
  • for $n = 4$, $(0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0)$ of length $19$ (and not $15$ as you suggested).

The construction of $\beta_{n+1}$ is obtnained by constructing a directed graph $G_n = (V_n, E_n)$ such that:

  • $V_n = \{0,1\}^n$ (vertices are words of length $n$);
  • for $u=u_1u_2…u_n, v=v_1v_2…v_n\in V_n$, there is an edge labelled by $v_n$ from $u$ to $v$ if and only if $u_2…u_n = v_1…v_{n-1}$.

A candidate (there are multiple possibilities) for the word $\beta_{n+1}$ is then the word obtained by reading edge's labels in an eulerian cycle.

To prove that $f(n)$ is indeed equal to $2^n+n-1$:

  • $f(n) \geqslant 2^n+n-1$ since the word constructed above has no repeated substring of length $n$ (because $\beta_n$ has no repeated circular substring of length $n$);
  • $f(n) \leqslant 2^n+n-1$ since there are $2^n$ different substring of length $n$, so there cannot be more than $2^n$ positions in the word that can be the beginning of a substring of length $n$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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