Cracking the Safe: Eulerian Path on De Bruijn Graph

You need to find the shortest possible string that contains every n-length combination of digits 0 through k-1 as a substring. That is the core of LeetCode 753: Cracking the Safe, and it turns out to be a beautiful application of graph theory.

The key insight is that this problem maps perfectly to a De Bruijn sequence. Instead of brute-forcing all possible combinations, you can model the problem as a directed graph where finding an Eulerian path (a path that visits every edge exactly once) gives you the shortest password. The resulting string has length k^n + n - 1, which is provably optimal.

Problem statement

Given two integers n and k, find the shortest string that contains every possible sequence of length n formed by digits 0 to k-1 as a substring. For example, with n=2 and k=2, the digits are 0 and 1, and the four possible combinations are 00, 01, 10, and 11. The shortest string containing all of them is "00110" (length 5), because 00 starts at index 0, 01 at index 1, 11 at index 2, and 10 at index 3.

There are k^n total combinations. A naive approach would concatenate all of them (length n * k^n), but adjacent combinations can share overlapping characters. The shortest password overlaps them maximally, giving a string of length k^n + n - 1.

Approach: DFS to find Eulerian path

The trick is to build a De Bruijn graph. Here is how it works:

• Nodes are all strings of length n-1 (there are k^(n-1) of them). Each node represents a "state" of the last n-1 digits you have entered.
• Edges represent all strings of length n (there are k^n of them). An edge from node u to node v with label d means: if the current state is u and you type digit d, the new state becomes v, and you have just entered the n-length combination u + d.

Finding a path that traverses every edge exactly once (an Eulerian path) means you have covered every n-length combination. Since this is a De Bruijn graph where every node has equal in-degree and out-degree (both equal to k), an Eulerian circuit is guaranteed to exist.

We use a DFS-based version of Hierholzer's algorithm. The DFS explores edges greedily, and when it backtracks, it appends the digits to the result in reverse. This naturally produces a valid Euler path.

def crack_safe(n: int, k: int) -> str:
    if n == 1:
        return "".join(str(i) for i in range(k))

    visited = set()
    result = []

    def dfs(node: str):
        for d in range(k):
            edge = node + str(d)
            if edge not in visited:
                visited.add(edge)
                dfs(edge[1:])
                result.append(str(d))

    start = "0" * (n - 1)
    dfs(start)
    return start + "".join(reversed(result))

Visual walkthrough

Let's trace through the algorithm with n=2, k=2. The two nodes are "0" and "1". The four edges are "00", "01", "10", "11". Watch how each step appends one digit and covers one new combination.

Notice how each new digit we append creates exactly one new 2-character substring. By the end, all four combinations appear as substrings of "00110". This is the Euler path in action: every edge (combination) gets visited exactly once, and the shared overlaps between consecutive edges keep the total length minimal.

Complexity analysis

The output string itself has length k^n + n - 1, so the algorithm is essentially optimal in both time and space relative to the output size.

Building blocks

1. De Bruijn graph construction

The core idea is encoding overlapping sequences as a graph. Each n-length string becomes an edge connecting its (n-1)-length prefix to its (n-1)-length suffix:

for d in range(k):
    edge = node + str(d)
    next_node = edge[1:]

The node is the current (n-1)-length state. Appending a digit d gives you the full n-length combination (the edge), and dropping the first character gives you the next node. This "sliding window on a graph" pattern shows up whenever you need to model overlapping sequences as transitions.

2. Hierholzer's algorithm for Eulerian path

Hierholzer's algorithm finds an Euler path by doing a DFS that removes edges as it goes. The key detail is that you build the path in reverse during backtracking:

def dfs(node: str):
    for d in range(k):
        edge = node + str(d)
        if edge not in visited:
            visited.add(edge)
            dfs(edge[1:])
            result.append(str(d))

When the DFS reaches a dead end (all edges from the current node have been visited), it backtracks and appends the digit. This post-order recording ensures that "dead-end" branches get placed at the beginning of the final path, producing a valid Euler circuit. If you append during the forward pass instead, you risk getting stuck in a subtour that misses some edges.

Edge cases

• n=1: Every single digit is a valid 1-length combination. The answer is just the string "0123...k-1". No graph needed.
• k=1: The only digit is 0. The only combination is n zeros. The answer is "000...0" (n zeros).
• n=1, k=1: The simplest case. The answer is "0".
• Large k^n: The output string can be very long (e.g., n=4, k=10 produces a string of length 10003). The algorithm still works, but watch for recursion depth limits in languages with limited stack size. An iterative version of Hierholzer's avoids this.
• Multiple valid answers: Many valid Euler paths exist. The problem accepts any shortest string that contains all combinations. The order you iterate digits (0, 1, ..., k-1) determines which valid answer you get.

From understanding to recall

You have seen how De Bruijn graphs transform an intimidating combinatorial problem into a clean graph traversal. The logic clicks when you read it. But in an interview, you need to reconstruct the graph model, remember why edges represent combinations (not nodes), write the DFS with post-order appending, and handle the n=1 edge case, all from memory. Those details slip away fast.

Spaced repetition bridges that gap. You practice building the De Bruijn graph from scratch, writing Hierholzer's DFS, and reversing the result at increasing intervals. After a few rounds, the pattern becomes automatic. You stop thinking about whether to append during forward or backward traversal because your fingers already know.

Related posts

• Course Schedule - Another graph problem where you build an adjacency list from scratch and run DFS, teaching the cycle detection pattern that complements Euler path techniques
• Reconstruct Itinerary - The closest relative to this problem, using Hierholzer's algorithm on a flight ticket graph to find an Eulerian path
• Word Ladder - BFS on an implicit state graph where each node is a word, showing how to model string transformations as graph traversal