Nearly De Bruijn sequences constructed from De Bruijn sequences Let $w$ be a De Bruijn $01$-sequence of the type $B(2,n)$; i.e., a cyclic $01$-sequence that contains every $n$-digit $01$-sequence exactly once.  Let $x$ be a $01$-sequence of length $n$.  When and how can one construct from $W$ a cyclic $01$-sequence $y$ that contains every $n$-digit $01$-sequence except $x$?
Example 1.  Let $w=01110100$, of type $B(2,3)$, and let $x=101$.  In $w$, replace $101$ by $1001$, resulting in $y=011100100$.  Since $y$ is cyclical, it contains every $3$-digit sequence except $x$.  Note that $100$ occurs twice, which is not disallowed.
Example 2.  For $w$ as above and $x=001$, there is no such $y$. 
 A: Each de Bruijn sequence corresponds to an Eulerian circuit in the de Bruijn graph $G$ (where arcs are labeled with $n$-mers and nodes are labeled with $(n-1)$-mers). The indegree and outdegree of each vertex is 2, so $G$ is Eulerian (i.e., de Bruijn sequence exists).
If $n$-mer $x$ is forbidden in a sequence, then we need to remove the arc labeled $x$ from $G$, resulting in a graph $G'$. This destroys the Eulerian property unless the arc was a self-loop (i.e., $x=0^n$ or $x=1^n$). In the latter case, the solution is trivial -- simply remove one 0 or 1 from the appearance of $x$. In the former case, we need to restore the Eulerian property by doubling some arcs in $G'$. 
Let $a$ and $b$ be $(n-1)$-mers representing the prefix and suffix of $x$, respectively. Then $G'$ lacks the arc $(a,b)$, and outdegree(a) = indegree(b) = 1, while indegree(a) = outdegree(b) = 2. To restore the balance, we need to find a trail from $a$ to $b$ in $G'$ and double every arc along this trail.
First, such trail exists as soon as $a$ and $b$ each contains both zeroes and ones (otherwise there is no way out of $a$ or into $b$).
Second, in order to construct the shortest such trail, let $c$ be the largest overlap of $y$ and $z$, where $y$ and $z$ are obtained from $x$ by inverting the last and first digit, respectively (notice that $y$ starts with $a$, while $z$ ends with $b$). So, $y=y'c$ and $z=cz'$. Then the trail we look for is encoded by the string $y'cz'$. In the original de Bruijn sequence, this corresponds to replacement of instance of $x$ with $y'cz'$. The sequence length is increased by $n-|c|$.
In summary:


*

*if $x=0^n$ or $1^n$, remove one digit from the instance of $x$ in the sequence.

*if $x=0^{n-1}1$, $1^{n-1}0$, $10^{n-1}$, or $01^{n-1}$, there is no solution.

*Otherwise replace the instance of $x$ in the sequence with $y'cz'$.
In the example with $x=101$, we have $y=100$, $z=001$, thus $c=00$ and $y'cz'=1001$.
