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 <= 4096Problem Overview: You need to generate the shortest possible string that guarantees opening a safe with an unknown password of length n, where each digit ranges from 0 to k-1. The string must contain every possible combination of length n exactly once as a substring. This is fundamentally a sequence generation problem that maps directly to graph traversal.
Approach 1: Backtracking with Visited Combinations (Time: O(k^n * n), Space: O(k^n))
This approach builds the sequence incrementally using Depth-First Search. Start with a prefix of n zeros, then repeatedly append digits from 0 to k-1. Each time you append a digit, form the last n-length substring and mark it as visited. If that combination hasn’t appeared before, continue the DFS. When all k^n combinations are visited, the constructed string is valid. Backtracking removes the last digit if a branch cannot cover all combinations. This method is conceptually simple and mirrors typical DFS permutation generation, but it becomes expensive as n grows because each recursive step checks and tracks visited states.
Approach 2: De Bruijn Sequence using Hierholzer's Algorithm (Time: O(k^n), Space: O(k^n))
The optimal solution models the problem as an graph. Each node represents a string of length n-1. Each directed edge represents appending a digit (forming a length n combination). Since every combination must appear exactly once, the task becomes finding an Eulerian circuit that visits every edge exactly once. Hierholzer’s algorithm performs a DFS traversal that consumes edges as they are visited. When traversing from node u, append digits 0..k-1, mark edges as used, and recursively explore the next node formed by the last n-1 characters. The resulting traversal naturally constructs a De Bruijn sequence. After DFS finishes, append the initial n-1 prefix to complete the cycle.
The key insight is that each edge corresponds to a unique password combination, so covering all edges exactly once ensures every possible password appears in the sequence. Instead of brute-forcing combinations, the algorithm systematically walks the graph structure that represents them.
Recommended for interviews: Interviewers usually expect the De Bruijn sequence solution with Hierholzer’s algorithm. It shows you recognize the transformation from substring coverage to Eulerian traversal. Explaining the backtracking version first demonstrates understanding of the search space, but implementing the graph-based approach proves stronger algorithmic maturity.
The problem can be transformed into finding a De Bruijn sequence for n-length and k-digit passwords. A De Bruijn sequence of order n over an alphabet of size k is a cyclic sequence in which every possible subsequence of length n appears as a sequence of consecutive characters exactly once. Hierholzer's algorithm can be used to find an Eulerian path/circuit, which forms the basis for constructing the desired De Bruijn sequence.
The code uses Depth First Search (DFS) to traverse all possible paths in our De Bruijn graph representation. Each node is a sequence and we attempt to append each possible digit (0 to k-1). If a sequence has not been seen, it is marked as visited. We recursively call DFS on the new node formed by appending the digit. Once a dead-end is reached, digits are added back to the result, which forms a De Bruijn sequence after appending the start node.
Python
JavaScript
Time Complexity: O(k^n).
Space Complexity: O(k^n) for the resulting sequence and visited nodes.
We can solve this problem using a backtracking approach by manually exploring each possible combination of digits and backtracking when a potential solution is found. Unlike the Eulerian path strategy, this approach builds sequences on-the-fly, exploring each digit combination and ensuring that all unique combinations appear in the sequence.
In this C++ solution, we use backtracking to explore every possible continuation of the current node. The DFS traverses possible sequences not yet visited and constructs the password by appending valid digits to the result. Recursively, it continues this process until all possible states are visited.
Time Complexity: O(k^n) due to recursive DFS explorations.
Space Complexity: O(k^n) for tracking visited states.
We can construct a directed graph based on the description in the problem: each point is considered as a length n-1 k-string, and each edge carries a character from 0 to k-1. If there is a directed edge e from point u to point v, and the character carried by e is c, then the last k-1 characters of u+c form the string v. At this point, the edge u+c represents a password of length n.
In this directed graph, there are k^{n-1} points, each point has k outgoing edges and k incoming edges. Therefore, this directed graph has an Eulerian circuit, and the path traversed by the Eulerian circuit is the answer to the problem.
The time complexity is O(k^n), and the space complexity is O(k^n).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| De Bruijn Sequence Using Hierholzer's Algorithm | Time Complexity: O(k^n). |
| Backtracking Approach | Time Complexity: O(k^n) due to recursive DFS explorations. |
| Eulerian Circuit | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Visited Set | O(k^n * n) | O(k^n) | Good for understanding the search space and demonstrating DFS logic in interviews |
| De Bruijn Sequence (Hierholzer's Algorithm) | O(k^n) | O(k^n) | Optimal solution when modeling the problem as a graph with Eulerian circuit traversal |
花花酱 LeetCode 753. Cracking the Safe - 刷题找工作 EP144 • Hua Hua • 9,778 views views
Watch 8 more video solutions →Practice Cracking the Safe with our built-in code editor and test cases.
Practice on FleetCode