Cracking the Safe
Last Updated: March 28, 2026
Understanding the Problem
This problem is asking us to construct the shortest possible string that contains every combination of n digits (drawn from 0 to k-1) as a contiguous substring. This is a classic problem in combinatorics known as a de Bruijn sequence.
Think about it this way: with n = 2 and k = 2, we have four possible passwords: "00", "01", "10", "11". We could naively concatenate them all to get "00011011" (length 8), but that is wasteful. Notice that consecutive passwords can overlap. The end of one password can serve as the beginning of the next. "01100" achieves the same coverage in just 5 characters by maximizing these overlaps.
The key observation is that this problem maps directly onto finding an Eulerian path in a specific graph. Each password of length n becomes an edge, and each prefix/suffix of length n-1 becomes a node. Finding a path that traverses every edge exactly once gives us the shortest string containing all passwords.
Key Constraints:
1 <= n <= 4and1 <= k <= 10→ The total number of passwords isk^n, which is at most 4096. This is a small search space, so even approaches with higher constant factors will pass.1 <= k^n <= 4096→ The output string length isk^n + n - 1, which is at most 4099 characters. Any reasonable algorithm will work within time limits.- The small constraints mean both backtracking and Hierholzer's algorithm are viable. The elegant solution models this as an Eulerian path problem.
Approach 1: DFS Backtracking
Intuition
The most direct way to think about this: we need to build a string that contains every possible n-digit combination as a substring. Start with a string of n zeroes (that is our first password). Then repeatedly try to extend by one character such that the last n characters form a new, previously unseen password.
If we hit a dead end where all extensions lead to passwords we have already seen, we backtrack. The backtracking ensures we find a valid path through all k^n passwords. We are essentially doing a DFS on the de Bruijn graph, but without explicitly constructing the graph.
Algorithm
- Start with a string of
nzeroes. Mark this as a visited password. - Use DFS: at each step, take the last
n-1characters of the current string as the current suffix. - Try appending each digit from
k-1down to0to form a candidate password of lengthn. - If the candidate has not been visited, mark it visited, append the digit to the result, and recurse.
- If the recursion reaches
k^nvisited passwords, we have found our answer. - If a branch fails, unmark the candidate and remove the appended digit (backtrack).
Example Walkthrough
Code
- Time Complexity: O(k^n * k). There are k^n passwords to visit, and at each step we try up to k digits. Backtracking is minimal since the de Bruijn graph guarantees a solution exists.
- Space Complexity: O(k^n * n). The visited set stores up to k^n strings of length n, and the recursion stack can go up to k^n levels deep.
The backtracking approach works but may explore dead-end branches. Since the de Bruijn graph is guaranteed to have an Eulerian circuit, can we use Hierholzer's algorithm to find the path directly without any backtracking?
Approach 2: Hierholzer's Algorithm (Eulerian Path)
Intuition
Model the problem as a directed graph where each node is a string of length n-1, and each edge is a password of length n connecting its prefix to its suffix. Each node has exactly k outgoing and k incoming edges, so the graph is Eulerian. Hierholzer's algorithm finds this circuit by doing a DFS with post-order edge collection: start at any node, follow edges greedily, and when stuck, append the digit to the result and backtrack through the recursion.
The de Bruijn graph is guaranteed to be Eulerian because every node has equal in-degree and out-degree (both equal to k). Hierholzer's algorithm exploits this: when you get "stuck" at a node with no unused edges, all remaining unvisited edges form sub-circuits. The post-order insertion weaves these sub-circuits into the main path, producing a valid Eulerian circuit that visits every edge exactly once.
Algorithm
- Handle the special case
n = 1by returning digits 0 through k-1 concatenated. - Build the de Bruijn graph implicitly: each node is a string of length
n-1, withkoutgoing edges. - Start DFS from the node consisting of
n-1zeroes. - At each node, try each digit 0 through k-1. If the resulting edge has not been visited, mark it and recurse.
- After exploring all edges from a node, append the current digit to the result (post-order).
- Append the starting node to the result at the end.
Example Walkthrough
Code
- Time Complexity: O(k^n). We visit each of the k^n edges exactly once. Each visit does O(1) amortized work for hash set lookup and insertion.
- Space Complexity: O(k^n * n). The visited set stores k^n strings of length n. The recursion stack can go k^n levels deep in the worst case.