There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].
The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.
"345" and you enter in "012345":
0, the most recent 3 digits is "0", which is incorrect.1, the most recent 3 digits is "01", which is incorrect.2, the most recent 3 digits is "012", which is incorrect.3, the most recent 3 digits is "123", which is incorrect.4, the most recent 3 digits is "234", which is incorrect.5, the most recent 3 digits is "345", which is correct and the safe unlocks.Return any string of minimum length that will unlock the safe at some point of entering it.
Example 1:
Input: n = 1, k = 2 Output: "10" Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.
Example 2:
Input: n = 2, k = 2 Output: "01100" Explanation: For each possible password: - "00" is typed in starting from the 4th digit. - "01" is typed in starting from the 1st digit. - "10" is typed in starting from the 3rd digit. - "11" is typed in starting from the 2nd digit. Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.
Constraints:
1 <= n <= 41 <= k <= 101 <= kn <= 4096Cracking the Safe is a classic graph problem that can be solved using the concept of a De Bruijn sequence. The goal is to generate the shortest string that contains every possible combination of length n using digits 0 to k-1. This can be modeled as a graph where each node represents a sequence of length n-1, and each edge corresponds to appending a digit to form a length n combination.
The key idea is to construct an Eulerian circuit in this directed graph so that every edge (i.e., every possible combination) is visited exactly once. A common implementation uses Depth-First Search (DFS) with a visited set to track used edges. During DFS, you append digits and explore new states while marking edges as used. By performing a post-order traversal (similar to Hierholzer’s algorithm), you can build the final sequence efficiently.
This approach ensures that all k^n combinations appear exactly once in the result while keeping the string length minimal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Eulerian Circuit (De Bruijn Graph) | O(k^n) | O(k^n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
We can think of this problem as the problem of finding an Euler path (a path visiting every edge exactly once) on the following graph: there are $$k^{n-1}$$ nodes with each node having $$k$$ edges. It turns out this graph always has an Eulerian circuit (path starting where it ends.) We should visit each node in "post-order" so as to not get stuck in the graph prematurely.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Cracking the Safe is considered an advanced graph problem and may appear in top-tier interviews. It tests knowledge of DFS, graph traversal, and advanced concepts like Eulerian paths and De Bruijn sequences.
A hash set or boolean set is typically used to track visited edges (combinations). Along with this, recursion or a stack is used for DFS traversal to build the sequence while exploring the De Bruijn graph.
An Eulerian circuit ensures every edge in a graph is visited exactly once. Since each edge represents a unique n-length combination, finding such a circuit guarantees that every combination is included without repetition while keeping the sequence minimal.
The optimal approach models the problem as a De Bruijn graph and finds an Eulerian circuit using DFS. Each node represents a sequence of length n-1 and edges represent appending digits. Traversing every edge exactly once guarantees all combinations appear in the final sequence.