Understanding De Bruijn Sequence: Theory and Practice

Introduction and Core Concepts

A De Bruijn sequence is one of the most elegant objects in combinatorics and string algorithms. For an alphabet of size k and a substring length n, a De Bruijn sequence B(k, n) is a cyclic string of length kⁿ in which every possible length-n string over that alphabet appears exactly once as a contiguous substring when the sequence is considered cyclically. This property of optimal packing makes it a minimal universal cycle for all n-length words.

The concept is named after the Dutch mathematician Nicolaas Govert de Bruijn, who studied these sequences in 1946, although their history traces back to Camille Flye Sainte-Marie in 1894 and even earlier to Sanskrit prosody. The classic example is the binary De Bruijn sequence for k=2 and n=3: 00010111. If we view this cyclically, its eight length-3 windows are 000, 001, 010, 101, 011, 111, 110, and 100 — precisely all 2³ = 8 binary strings of length 3, each exactly once.

Why does this matter for computer science? De Bruijn sequences solve the problem of generating the shortest possible string that contains every n-gram. Instead of naively concatenating all kⁿ strings, which would require n * kⁿ characters, a De Bruijn sequence achieves the same coverage in only kⁿ characters (plus n-1 characters if linearized). This exponential saving is critical in applications ranging from genome assembly and combinatorial testing to robotics, cryptography, and hardware testing. Understanding its theory provides deep insight into Eulerian graphs, Lyndon words, and universal cycles.

Formal Definition

Let Σ be an alphabet with |Σ| = k. A De Bruijn sequence B(k, n) is a cyclic sequence A = a₀a₁...a_kⁿ-1 such that for every string s ∈ Σⁿ, there exists a unique i where s = a_ia_i+1...a_i+n-1 with indices taken modulo kⁿ. When linearized for practical use, we typically append the first n-1 characters to the end, yielding a linear string of length kⁿ + n - 1 that contains every n-length word as a linear substring.

It is important to distinguish between the cyclic and linear forms. The cyclic form is mathematically pure and has length exactly kⁿ, while the linear form is what you store in a file or transmit over a network. For example, the cyclic binary sequence for n=2 is 0011 (windows: 00, 01, 11, 10). Its linear form is 00110, where the final 0 is the wrap-around.

Intuition: Why Length kⁿ is Optimal

A string of length L contains L distinct windows of length n when viewed cyclically, or L - n + 1 windows linearly. To cover kⁿ distinct substrings, we need at least kⁿ windows, so L must be at least kⁿ cyclically. A De Bruijn sequence meets this lower bound with equality, proving its optimality. No shorter cyclic string can contain all n-mers, and any string that does must be a De Bruijn sequence up to rotation. This optimality is why De Bruijn sequences are often called complete cycles or universal cycles.

How It Works

The existence and construction of De Bruijn sequences are best understood through graph theory. There are two equivalent graph formulations, both of which reveal why these sequences must exist and how to generate them efficiently.

The De Bruijn Graph

The De Bruijn graph G(k, n) is a directed graph where vertices represent all strings of length n-1 over Σ, and edges represent strings of length n. Specifically, there are k^n-1 vertices and kⁿ edges. An edge labeled a₁a₂...a_n goes from vertex a₁...a_n-1 to vertex a₂...a_n. In this graph, every vertex has in-degree k and out-degree k, making it balanced and strongly connected. By Euler's theorem, such a graph is Eulerian — it contains a cycle that traverses every edge exactly once.

Reading the edge labels along an Eulerian cycle yields a De Bruijn sequence. For example, with k=2, n=3, vertices are {00, 01, 10, 11}. The edge 001 goes from 00 to 01, edge 011 goes from 01 to 11, and so on. An Eulerian cycle that visits all 8 edges in order corresponds directly to the sequence 00010111. The alternative formulation uses vertices as n-length strings and edges as overlaps of n+1, where a Hamiltonian cycle corresponds to the sequence. The Eulerian view is computationally preferable because Eulerian cycles can be found in linear time, while Hamiltonian cycles are NP-hard in general graphs.

The graph perspective also explains why the number of distinct De Bruijn sequences is so large. The number of distinct Eulerian cycles in G(k, n) is given by the BEST theorem (de Bruijn, van Ebbenhorst Tengbergen, Smith, Tutte): (k! )^kn-1-1 / k^n-1 multiplied by k^n-1! . For binary alphabets this simplifies to 2^{2n-1 - n}. For n=4, there are already 16 distinct binary sequences; for n=5, there are 2048.

Lyndon Words and the FKM Algorithm

The second deep mechanism is the FKM algorithm, named after Fredericksen, Kessler, and Maiorana. It constructs the lexicographically smallest De Bruijn sequence (often called the prefer-smallest or Ford sequence) by concatenating Lyndon words whose lengths divide n in lexicographic order. A Lyndon word is a string that is strictly smaller in lexicographic order than all of its nontrivial rotations — for example, 001 is Lyndon, but 010 is not because its rotation 001 is smaller.

The theorem states: Concatenate all Lyndon words whose length divides n, in lexicographic order, and you obtain a De Bruijn sequence. For k=2, n=3, the Lyndon words with lengths dividing 3 are 0, 001, 011, 1. Concatenating them gives 0 001 011 1 = 00010111, which is exactly the sequence we saw earlier. This construction is remarkable because it generates the sequence without explicitly building the graph, using only string comparison and recursion, and it runs in optimal time and space.

Cyclic Overlap and Universal Cycles

At its core, a De Bruijn sequence exploits maximal overlap between consecutive n-mers. Two consecutive windows share n-1 characters. For instance, in 00010111, the window 001 is followed by 010, overlapping on 01. This overlap of n-1 is the maximum possible, which is why the total length is minimized. Any universal cycle for a combinatorial family must exhibit this property, and De Bruijn sequences are the prototypical example of universal cycles, a broader class that includes universal cycles for permutations, subsets, and partitions.

Implementation

There are two canonical ways to implement De Bruijn sequence generation in Python: the recursive FKM algorithm for the lexicographically smallest sequence, and the iterative Hierholzer's algorithm for finding an Eulerian cycle in the De Bruijn graph. Both run in O(kⁿ) time, which is optimal since the output itself has that length, but they differ in clarity, memory usage, and flexibility.

Method 1: FKM Algorithm (Lyndon Word Concatenation)

The FKM algorithm is the most concise and memory-efficient method. It generates the sequence in lexicographic order using a recursive helper that builds necklaces. It uses only O(kⁿ) time and O(n) auxiliary space beyond the output.

def de_bruijn_fkm(k, n):
    """
    Generate lexicographically smallest de Bruijn sequence for alphabet 0..k-1
    using FKM algorithm (Lyndon word concatenation).
    Returns cyclic sequence as string of length k**n.
    k: alphabet size, n: substring length
    """
    alphabet = [str(i) for i in range(k)]
    a = [0] * k * n
    sequence = []

    def db(t, p):
        # t: current position, p: period of current Lyndon word
        if t > n:
            if n % p == 0:
                # length p divides n, add Lyndon word to sequence
                for j in range(1, p + 1):
                    sequence.append(alphabet[a[j]])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)

    db(1, 1)
    return "".join(sequence)

# Example: binary alphabet, n=3
print(de_bruijn_fkm(2, 3))  # Output: 00010111
print(de_bruijn_fkm(2, 4))  # Output: 0000100110101111

Method 2: Eulerian Cycle via Hierholzer's Algorithm

This method explicitly models the De Bruijn graph and finds an Eulerian cycle. It is more intuitive for those familiar with graph algorithms and allows easy generation of different sequences by changing the order in which edges are visited. It uses iterative DFS with a stack to avoid recursion limits for large n.

def de_bruijn_hierholzer(k, n):
    """
    Generate de Bruijn sequence via Eulerian cycle in De Bruijn graph.
    Uses iterative Hierholzer's algorithm. Returns cyclic sequence.
    """
    if n == 1:
        return "".join(str(i) for i in range(k))

    # Number of vertices = k**(n-1), edges = k**n
    # Represent vertex as integer 0 .. k**(n-1)-1 in base k
    alphabet = [str(i) for i in range(k)]
    num_vertices = k ** (n - 1)

    # adjacency pointer: next edge to explore for each vertex
    next_edge = [0] * num_vertices
    stack = [0]  # start at vertex 0...0
    circuit = []  # stores edge labels in reverse

    while stack:
        v = stack[-1]
        if next_edge[v] < k:
            # explore next outgoing edge labeled next_edge[v]
            c = next_edge[v]
            next_edge[v] += 1
            # compute next vertex: shift left and add c
            # v represents digits d1..d_{n-1}, next is d2..d_{n-1},c
            next_v = (v * k + c) % num_vertices
            stack.append(next_v)
            circuit.append(c)
        else:
            stack.pop()

    # circuit holds edge labels in reverse order; build sequence
    # The Eulerian cycle length is k**n, circuit length is k**n
    circuit.reverse()
    # Start with n-1 zeros (starting vertex), then append circuit
    seq = "0" * (n - 1) + "".join(alphabet[c] for c in circuit)
    # For cyclic sequence, trim to k**n characters
    return seq[:k**n]

print(de_bruijn_hierholzer(2, 3))  # One valid sequence, e.g., 00010111

Method 3: Verification and Linearization Utilities

Generating a sequence is only half the task; you must verify that every n-mer appears exactly once. This utility also shows how to convert a cyclic sequence to its linear form for storage or transmission.

def verify_de_bruijn(seq, k, n, is_cyclic=True):
    """
    Verify that seq is a valid de Bruijn sequence B(k,n).
    Checks that every n-length word over alphabet 0..k-1 appears exactly once.
    """
    alphabet = set(str(i) for i in range(k))
    expected_len = k ** n
    if len(seq) != expected_len:
        return False, f"Length {len(seq)} != expected {expected_len}"

    if not set(seq).issubset(alphabet):
        return False, "Alphabet mismatch"

    seen = set()
    # For cyclic sequence, wrap around
    extended = seq + seq[:n-1] if is_cyclic else seq
    num_windows = expected_len if is_cyclic else len(seq) - n + 1

    for i in range(num_windows):
        window = extended[i:i+n]
        if window in seen:
            return False, f"Duplicate window {window} at position {i}"
        seen.add(window)

    if len(seen) != k ** n:
        return False, f"Missing windows: expected {k**n}, got {len(seen)}"
    return True, "Valid de Bruijn sequence"

def linearize(seq, n):
    """Convert cyclic de Bruijn sequence to linear form."""
    return seq + seq[:n-1]

# Verification example
seq = de_bruijn_fkm(2, 3)
print(verify_de_bruijn(seq, 2, 3))  # (True, 'Valid de Bruijn sequence')
print(linearize(seq, 3))            # 0001011100

Method 4: Generalized Alphabet and Prefer-Suffix Construction

For non-binary alphabets or custom symbol sets, such as DNA bases or alphanumeric characters, the same algorithms generalize. This example shows a prefer-largest construction and supports arbitrary alphabets.

def de_bruijn_general(alphabet, n):
    """
    Generate de Bruijn sequence for arbitrary alphabet list.
    alphabet: list of symbols e.g., ['A','C','G','T'] for DNA
    n: substring length
    Uses FKM generalized to any alphabet size.
    """
    k = len(alphabet)
    a = [0] * k * n
    seq_indices = []

    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    seq_indices.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)

    db(1, 1)
    # Map indices to actual symbols
    return "".join(alphabet[i] for i in seq_indices)

# DNA example: all 3-mers over {A,C,G,T}, length 4**3 = 64
dna_seq = de_bruijn_general(['A','C','G','T'], 3)
print(dna_seq[:20], "... length:", len(dna_seq))
print(verify_de_bruijn(dna_seq, 4, 3))

Step-by-Step Example

To make the theory concrete, let us walk through the complete construction of the binary De Bruijn sequence B(2, 3) using both the graph method and the FKM method. Our goal is to generate a cyclic string of length 8 that contains all 8 binary strings of length 3.

Step 1: Enumerate All n-mers

For k=2, n=3, the set of all 3-mers is: 000, 001, 010, 011, 100, 101, 110, 111. There are exactly 2³ = 8 of them. A naive concatenation would be 000001010011100101110111 (length 24), but we can do much better by overlapping.

Step 2: Build the De Bruijn Graph G(2, 3)

Vertices are all 2-mers: 00, 01, 10, 11. Edges are the 3-mers, connecting prefix to suffix. For instance, edge 001 connects 00 -> 01, edge 010 connects 01 -> 10, edge 101 connects 10 -> 01. Each vertex has exactly 2 outgoing and 2 incoming edges. The adjacency list is: 00 -> {000, 001}, 01 -> {010, 011}, 10 -> {100, 101}, 11 -> {110, 111}.

Step 3: Find an Eulerian Cycle

We start at vertex 00. One possible Eulerian cycle, found via Hierholzer's algorithm, traverses edges in this order: 000 (00->00), 001 (00->01), 011 (01->11), 111 (11->11), 110 (11->10), 101 (10->01), 010 (01->10), 100 (10->00) and returns to start. If we write down the first character of each edge label in order, we get 0 0 0 1 1 1 0 1, but the standard reconstruction appends the last n-1 characters of the final vertex. More directly, starting with 00 and appending the last character of each traversed edge gives: start 00 + 0 (from 000) + 1 (from 001) + 1 (from 011) + 1 (from 111) + 0 (from 110) + 1 (from 101) + 0 (from 010) + 0 (from 100) = 0001110100, which cyclically is 00010111 after rotation. Different Eulerian cycle orderings produce different but equally valid sequences, such as 00011101.

Step 4: Verify via FKM Concatenation

Using the FKM method, we list Lyndon words whose lengths divide 3 in lexicographic order: length 1: 0, 1; length 3: 001, 011. Note that 010 is not Lyndon, and 000 and 111 are not Lyndon because they are repetitions. Sorted order: 0, 001, 011, 1. Concatenating yields 0 + 001 + 011 + 1 = 00010111. To verify, we slide a window of length 3 cyclically: positions 0-2: 000, 1-3: 001, 2-4: 010, 3-5: 101, 4-6: 011, 5-7: 111, 6-0 (wrap): 110, 7-1 (wrap): 100. All 8 appear exactly once, confirming correctness.

Step 5: Linearize for Practical Use

If you need to use this sequence to test a combination lock that checks every 3 consecutive digits, you would use the linear form 0001011100 (length 10 = 8 + 2). Feeding this string sequentially into the lock guarantees that every 3-digit combination is tried with minimal key presses. The two extra characters at the end are simply the first n-1 = 2 characters repeated to handle the wrap-around without needing a cyclic buffer.

Complexity Analysis

Complexity analysis for De Bruijn sequences must consider both the generation cost and the properties of the output. Since the output size itself is exponential in n (kⁿ), any algorithm that explicitly constructs the sequence must take at least exponential time and space. The key question is whether the algorithm adds overhead beyond this inherent cost.

The FKM algorithm is optimal: it generates each character in amortized O(1) time, for total O(kⁿ) time and O(kⁿ) space for the output plus O(n) auxiliary space. Hierholzer's algorithm also runs in O(kⁿ) time because it visits each of the kⁿ edges exactly once, but it requires O(kⁿ) space to store the graph's adjacency pointers if implemented naively, or O(k^n-1) for the vertex stack. Verification by hashing all windows takes O(kⁿ * n) time if windows are copied naively, but can be optimized to O(kⁿ) using rolling hash.

Best, average, and worst cases are essentially identical for generation because the output size is fixed for given k and n; there is no input-dependent variation. However, the constant factors differ: FKM has very low overhead, while graph-based methods may have higher constants due to stack management and modulo arithmetic. For very large n (e.g., n > 20 for binary), explicit generation becomes infeasible due to memory, and implicit or streaming generation is required.

For practical purposes, the dominant factor is kⁿ. Even for modest parameters, this grows quickly: B(2, 10) has length 1,024, B(2, 20) has length 1,048,576, and B(4, 10) for DNA has length 1,048,576 as well. For k=26 and n=4, the length is 456,976. This exponential growth means that De Bruijn sequences are most useful when n is small (typically n <= 12 for binary) or when generated on-the-fly without storing the entire sequence.

Amortized Analysis of FKM

The FKM recursion generates each Lyndon word exactly once and each character is appended once. The total number of recursive calls is proportional to the number of necklaces, which is O(kⁿ / n). Since each call does O(1) work amortized, the total time is linear in output size. This is a rare example of a combinatorial generation algorithm that achieves optimal amortized constant time per output element.

Variations and Optimizations

While the classic De Bruijn sequence covers all kⁿ strings exactly once, many applications require variants that adapt the core idea to different constraints, alphabets, or cost models.

Prefer-Suffix and Prefer-Opposite Algorithms

The FKM algorithm generates the lexicographically smallest sequence (prefer-0). By modifying the traversal order, you can generate the lexicographically largest (prefer-1) or any prefer-suffix sequence. The classic prefer-one algorithm for binary alphabets works greedily: start with n zeros, then repeatedly try to append 1 if the resulting n-mer has not been seen, otherwise append 0. This greedy algorithm also produces a valid De Bruijn sequence and is often easier to implement for interview settings, though its naive implementation is O(kⁿ * n) due to substring checks.

Doubly-Extended and Complement Variants

For error-correcting codes, you may want a sequence where not only every n-mer appears, but also its complement or reverse complement appears at a controlled distance. Complemented De Bruijn sequences are useful in DNA synthesis where you want to avoid secondary structures. Another variant is the universal cycle for weight-constrained strings, where only strings with a given Hamming weight are included, useful for testing circuits with limited power consumption.

Memory-Optimized Streaming

When kⁿ is too large to store, you can generate the sequence as a stream using O(n) memory. The FKM algorithm can be made iterative to output characters one by one without storing the entire sequence. Similarly, a feedback shift register (FSR) approach can generate binary De Bruijn sequences using a linear or nonlinear feedback function. For binary alphabets, a maximal-length LFSR with a primitive polynomial generates a De Bruijn-like sequence of length 2ⁿ - 1 (missing the all-zero word), which can be patched to a full De Bruijn sequence by inserting an extra zero.

Higher-Dimensional De Bruijn Tori

The concept generalizes to two dimensions: a De Bruijn torus is a 2D array where every possible n x m pattern appears exactly once. These are used in computer vision for structured light patterns and in robotics for position encoding. Construction uses similar graph techniques but with 2D De Bruijn graphs where vertices are (n-1) x (m) or (n) x (m-1) subarrays.

Real-World Applications

De Bruijn sequences are not merely theoretical curiosities; they appear in surprisingly diverse practical systems where exhaustive coverage with minimal length is valuable.

In bioinformatics, De Bruijn graphs are the foundation of modern genome assemblers such as Velvet, SPAdes, and Trinity. Sequencing machines produce millions of short reads (length 100-300). To reconstruct the original genome, assemblers break reads into k-mers (typically k=31 to 77) and build a De Bruijn graph where each distinct k-mer is an edge. An Eulerian path through this graph corresponds to the assembled genome. While this is a graph rather than a single sequence, the underlying mathematics is identical, and the efficiency of De Bruijn graph traversal enables assembly of gigabase-scale genomes.

In cybersecurity and hardware testing, De Bruijn sequences provide minimal test patterns. A digital circuit with n binary inputs has 2ⁿ possible input combinations. To test for stuck-at faults, you need to apply all combinations. Feeding a De Bruijn sequence of length 2ⁿ + n - 1 to the circuit achieves complete coverage with minimal test time. Similarly, combination locks and keypads can be cracked optimally: a lock that checks the last n digits entered can be opened by entering a De Bruijn sequence, trying every combination without resetting.

Robotics and computer vision use De Bruijn sequences for absolute position encoding. A common technique is to print a De Bruijn sequence along a track or around a wheel using two colors or magnetic poles. A sensor that reads n consecutive symbols can determine its absolute position uniquely, because each n-mer appears only once. This is used in linear encoders, rotary encoders, and even in the pattern of dots on Anoto digital paper. The 2D torus variant projects a pattern onto a surface so a camera can determine its pose from a small window.

In distributed systems and networking, De Bruijn graphs define an optimal network topology. A De Bruijn network with kⁿ nodes has degree 2k and diameter n, providing logarithmic diameter with constant degree, which is ideal for peer-to-peer DHTs like Koorde. Routing can be done by shift operations on node IDs, making it simple and load-balanced. In cryptography, De Bruijn sequences are used to generate pseudo-random sequences with good statistical properties and to construct stream ciphers where the keystream must contain all n-grams uniformly.

Everyday Example: The Magic Trick

A classic magic trick uses a De Bruijn sequence to appear to predict cards. The magician arranges 32 cards in order 00000100011001010011101011011111 where red=0 and black=1. Any 5 consecutive cards encode a unique 5-bit number (0-31), allowing the magician to determine the position of a cut. The audience perceives randomness, but the sequence guarantees uniqueness.

Comparison with Alternatives

De Bruijn sequences are optimal for exhaustive n-mer coverage, but they are not always the right tool. Depending on constraints such as alphabet size, error tolerance, or the need for random access, alternative approaches may be preferable.

Brute-force concatenation simply lists all kⁿ strings with separators, using n * kⁿ characters. It is trivial to implement and allows O(1) random access to the i-th string, but it is n times longer than a De Bruijn sequence. Universal cycles generalize De Bruijn sequences to other combinatorial families like permutations or subsets, but they may not exist for all families and often require more complex constructions. Lyndon word generation is not an alternative but the underlying mechanism for FKM; however, generating Lyndon words independently is useful for necklace enumeration. Finally, a De Bruijn graph can be used directly without extracting a sequence, which is preferable when you need to store and query k-mers rather than generate a linear string, as in genome assembly where the graph is sparse.

In practice, the choice depends on whether you need a linear string or a data structure. If you are generating a test sequence to feed into hardware, a De Bruijn sequence is ideal. If you are building a k-mer index for a genome assembler where only a fraction of all possible k-mers actually appear in the reads, storing the full De Bruijn sequence would be wasteful; instead, you store the sparse De Bruijn graph using hash tables or Bloom filters. For teaching or small n, brute force is acceptable, but it quickly becomes infeasible as n grows.

Common Mistakes and Best Practices

Implementing and using De Bruijn sequences correctly requires attention to several subtle pitfalls that frequently trap developers and students.

Mistake 1: Forgetting Cyclic vs Linear Distinction

The most common error is treating a cyclic sequence of length kⁿ as if it linearly contains all windows. It does not — you need kⁿ + n - 1 characters linearly. For example, 0011 cyclically contains 10 via wrap-around, but linearly 0011 only contains 00, 01, 11. Always linearize by appending the first n-1 characters when you need linear substring search, and document whether your API returns cyclic or linear form.

Mistake 2: Inefficient Verification with String Slicing

A naive verification that slices n-length substrings in a loop and inserts them into a Python set takes O(kⁿ * n) time due to copying. For large n, this becomes a bottleneck. Best practice is to use a rolling hash or to encode n-mers as integers in base k and update in O(1) per window: new_code = (old_code * k + new_digit) % kⁿ. This reduces verification to O(kⁿ) time and avoids excessive string allocation.

Mistake 3: Recursion Depth and Integer Overflow

The recursive FKM implementation can hit Python's recursion limit when n is large (e.g., n > 1000) because recursion depth equals n. Use an iterative version or increase sys.setrecursionlimit. Similarly, computing k**n directly can overflow memory or create huge integers; always check whether kⁿ fits in memory before attempting generation. For k=2, n=30, kⁿ is about 1 billion characters — far beyond typical RAM.

Mistake 4: Assuming Uniqueness

There are many distinct De Bruijn sequences for the same k and n (exponentially many). Do not assume that two correct implementations will produce the same string; they may produce different Eulerian cycles. If you need deterministic output for testing, always specify the construction method (e.g., lexicographically smallest via FKM) and the starting vertex. When comparing sequences, compare their sets of n-mers, not the strings themselves.

Best Practices

• Always validate parameters: k >= 2, n >= 1, and that k**n is feasible to generate and store.
• Provide both cyclic and linear APIs, with clear naming like de_bruijn_cyclic() and de_bruijn_linear().
• Use integer encoding for alphabets larger than 10 to avoid multi-character symbols causing ambiguity; return a list of integers or symbols rather than a concatenated string when symbols are not single characters.
• For production use, prefer iterative Hierholzer with explicit stack to avoid recursion limits and to allow streaming.
• Include a verification function in your test suite that checks coverage and uniqueness, and test on small cases where brute force is feasible (k=2, n=3,4).
• Document time and space complexity prominently so users understand exponential growth.

Interview Questions

De Bruijn sequences are a favorite in algorithm interviews because they combine graph theory, string algorithms, and combinatorial reasoning. Here are common questions and how to approach them.

Question 1: Cracking the Safe (LeetCode 753)

Problem: A safe has a 4-digit PIN (each digit 0-9) and checks the last 4 digits entered. Find the shortest string that guarantees opening the safe. This is exactly B(10, 4), length 10,000. The expected solution is to model it as a De Bruijn graph with 10³ = 1000 vertices and find an Eulerian cycle via DFS. Interviewers expect you to recognize the De Bruijn graph reduction and implement Hierholzer's algorithm. The optimal answer is O(kⁿ) time, and you should mention the need to linearize by appending n-1 characters if the safe checks linearly. A follow-up is to handle arbitrary k and n.

Question 2: Generate Binary De Bruijn Sequence

Problem: Write a function to generate a binary De Bruijn sequence for n=3. Explain why your sequence is correct. A concise answer is to present the prefer-one greedy algorithm or FKM, generate 00010111, and then demonstrate verification by enumerating all 8 windows. The interviewer is testing whether you understand the Eulerian cycle argument and can argue optimality (length 8 is minimal). Be prepared to prove that your algorithm visits each edge exactly once and that the graph is Eulerian.

Question 3: Find the De Bruijn Sequence Containing a Given Pattern

Problem: Given k, n, and a pattern p of length n, find the position of p in the lexicographically smallest De Bruijn sequence without generating the entire sequence. This tests deeper understanding. The position of p corresponds to the rank of its Eulerian cycle traversal. One approach is to simulate FKM generation until p appears, but a more efficient method uses Lyndon word factorization to compute the rank combinatorially. For small n, generating the full sequence is acceptable, but you should discuss the trade-off and mention that direct ranking can be done in O(n) using Duval's algorithm for Lyndon factorization.

Question 4: De Bruijn Graph vs De Bruijn Sequence — When to Use Which?

Problem: You are building a genome assembler. Would you store a De Bruijn sequence or a De Bruijn graph? Why? The correct answer is the graph, because the genome is not a De Bruijn sequence covering all possible k-mers; it only contains the k-mers present in the reads, which is a sparse subset. Storing the full sequence of length 4^k is impossible for k=31. Instead, you store the observed k-mers as edges in a hash table, and assembly corresponds to finding an Eulerian path that uses only observed edges. This demonstrates understanding of practical constraints versus theoretical optimality.

Question 5: Count Distinct De Bruijn Sequences

Problem: How many distinct binary De Bruijn sequences exist for n=3? How would you count them for general k, n? For n=3, k=2, the answer is 2^{22 - 3} = 2, but more generally the count is given by the BEST theorem: (k! )^{kn-1 - 1} * (k^n-1)! / k^n-1. For binary, this simplifies to 2^{2n-1 - n}. The interviewer wants to see familiarity with the BEST theorem and Eulerian cycle counting, and the ability to explain why the number grows doubly exponentially. You should also mention that counting is distinct from generation, and that enumeration of all sequences is infeasible for large n.

Mastering these questions requires not just coding the generation, but articulating the graph theory behind it, analyzing complexity, and connecting to real-world constraints. Practicing both the FKM and Hierholzer implementations will ensure you can adapt to any variant the interviewer presents.