---
title: "De Bruijn Sequences"
summary: "The shortest string containing every k-mer: an Eulerian cycle on (k−1)-bit states."
difficulty: hard
tags: [euler, strings, construction]
time: k + 2^k
see: [euler/hierholzer, structures/trie]
---

A **de Bruijn sequence** $B(k, n)$ is a cyclic string over an alphabet of size $k$ in which every length-$n$ word appears exactly once as a (cyclic) substring. Its length is $k^n$, and it is optimal: $k^n$ distinct windows need at least $k^n$ positions.

:::idea title="The reduction, in one picture"
Vertices = the $k^{n-1}$ words of length $n-1$. For each vertex $w = a_1 \dots a_{n-1}$ and each letter $b$, add an edge $w \to a_2 \dots a_{n-1} b$ labelled $b$.
Every vertex then has out-degree $k$ and in-degree $k$, and the graph is strongly connected (shift away any window). So it is Eulerian (@euler/euler-existence), and an Eulerian *circuit* uses each edge once — each edge is exactly one length-$n$ word (its label plus the tail of the source). Reading edge labels along the tour gives $B(k,n)$.
:::

```cpp debruijn.cpp
int k, n, N;                                  // N = k^(n-1)
vector<int> a(k * n), result;
vector<int> ptr;                              // per-vertex next letter to try

void dbg(int v) {                             // Hierholzer on implicit graph
    for (int& c = ptr[v]; c < k; c++) {
        int nxt = (v * k + c) % N;
        dbg(nxt);
        result.push_back(c);                  // append on the way BACK
    }
}
// result reversed (as built by the recursion) = the sequence, length k^n
```

:::theorem title="Why append-on-return is correct here"
`dbg` is Hierholzer's post-order emission (@euler/hierholzer): the letters recorded on unwinding are exactly the tour read in reverse, and reversing a cyclic Euler tour is a cyclic Euler tour. That is why no explicit reversal is needed when only the cyclic sequence matters.
:::

## Prefer the greedy (FKM) version
There is a slicker construction whose output is the *lexicographically smallest* sequence: the **Lyndon-word concatenation** (Fredericksen–Kessler–Maiorana). Generate in DFS order all Lyndon words whose length divides $n$, concatenated:

```cpp fkm.cpp
int k, n; vector<int> a(k * n);
string seq;
void db(int t, int p) {                       // t = length, p = period
    if (t > n && n % p == 0)
        for (int i = 1; i <= p; i++) seq.push_back(char('0' + a[i]));
    else {
        a[t + p] = a[t];                       // extend periodically…
        db(t + 1, p);
        for (int j = a[t] + 1; j < k; j++) { a[t] = j; db(t + 1, t); }
    }
}
db(1, 1);
```
Same $O(k^n)$ output size, constant memory beyond the array, and it needs no graph at all — a nice example of "the graph was in your head the whole time".

:::props title="What these are good for"
- **combination locks / brute force**: to try all 4-digit PINs on a wheel you need $10^4 + 3$ turns, not $4 \cdot 10^4$ — a de Bruijn sequence $B(10,4)$, linear instead of $k$-times linear,
- **DNA sequencing / assembly**: reads are exactly $k$-mers, and the overlap graph is a de Bruijn graph — real genome assemblers (SPAdes and descendants) build and simplify de Bruijn graphs, and "contig = Eulerian path after compressing degree-2 chains",
- **testing**: any $k^n$-long test stream hits every length-$n$ configuration exactly once (registers, sequences, card tricks),
- **lower bounds**: the argument "windows ↔ edges" proves the length bound and the construction at the same time.
:::

:::figure src="De_Bruijn_Graph.svg" caption="The de Bruijn graph for $B(2,3)$: four vertices (2-bit states), eight edges (3-bit words). Every vertex has in-degree = out-degree = 2, so an Euler circuit exists and is the sequence."
:::

:::note title="Line version vs cycle version"
A *linear* string containing all $k^n$ words needs $k^n + n - 1$ characters (take the cyclic sequence and repeat its first $n-1$ symbols at the end). Problems that ask for "a string" rather than "a cyclic string" are asking for that $+n-1$; forgetting it is a wrong answer, not an off-by-one style issue.
:::

:::problems
- [[CSES 1692]] De Bruijn Sequence | https://cses.fi/problemset/task/1692 | core | exact output checker
- [[CSES 2205]] Gray Code | https://cses.fi/problemset/task/2205 | easy | Hamiltonian cycle on $Q_n$, same framing
:::