Largest binary sequency with no repeated subsequences that have a fixed length

Question

$A$ is an ordered sequence of elements $a_i=0,1$ containing no repeated sub-sequences [$a_i,a_{i+k}$).

Example

The sequence $(0, 1, 1, 0, 1, 0, 1, 1, 1, 0)$ and a sub-sequence length $k=4$ produces the sub-sequences:

$(0, 1, 1, 0)$, $(1, 1, 0, 1)$, $(1, 0, 1, 0)$, $(0, 1, 0, 1)$, $(1, 0, 1, 1)$, $(0, 1, 1, 1)$, $(1, 1, 1, 0)$

Since all sub-sequences are unique, this sequence satisfies the condition.

Counterexample

The sequence $(1, 0, 1, 0, 1)$ and a sub-sequence length $k=3$ produces the sub-sequences:

$(1, 0, 1)$, $(0, 1, 0)$, $(1, 0, 1)$

The first and last sub-sequence is the same and therefore this sequence fails.

Question

Given $k$, what is the longest passing sequence that can be generated?

Is there a polynomial time algorithm to generate such a sequence?

Related posts

• Largest binary sequence with no more than two repeated subsequences

• Infinite sequence of digits without consecutive repeating subsequenes