Skip to main content
Talentd

Cracking the Safe - Solution & Explanation

HardDepth-First SearchGraphEulerian Circuit12 min readAsked at: Google
Practice this problem

Problem Statement

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.

  • For example, the correct password is "345" and you enter in "012345":
    • After typing 0, the most recent 3 digits is "0", which is incorrect.
    • After typing 1, the most recent 3 digits is "01", which is incorrect.
    • After typing 2, the most recent 3 digits is "012", which is incorrect.
    • After typing 3, the most recent 3 digits is "123", which is incorrect.
    • After typing 4, the most recent 3 digits is "234", which is incorrect.
    • After typing 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 <= 4
  • 1 <= k <= 10
  • 1 <= kn <= 4096

Approach Overview

Problem 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.

Approach 1: De Bruijn Sequence Using Hierholzer's Algorithm

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(k^n).
Space Complexity: O(k^n) for the resulting sequence and visited nodes.

Try this approach in the editor →

Approach 2: Backtracking Approach

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(k^n) due to recursive DFS explorations.
Space Complexity: O(k^n) for tracking visited states.

Try this approach in the editor →

Approach 3: Eulerian Circuit

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
De Bruijn Sequence Using Hierholzer's Algorithm

Time Complexity: O(k^n).
Space Complexity: O(k^n) for the resulting sequence and visited nodes.

Backtracking Approach

Time Complexity: O(k^n) due to recursive DFS explorations.
Space Complexity: O(k^n) for tracking visited states.

Eulerian Circuit—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Visited SetO(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

Video Solution

花花酱 LeetCode 753. Cracking the Safe - 刷题找工作 EP144 • Hua Hua • 9,797 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Cracking the Safe easy or hard?
Cracking the Safe is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that the task maps to generating a De Bruijn sequence and solving it using an Eulerian circuit in a directed graph rather than brute-force combination generation.
Cracking the Safe Python/Java solution
Most implementations build the De Bruijn sequence using DFS and a visited set of edges. Python and JavaScript solutions typically implement Hierholzer's algorithm recursively, while C++ and Java versions often demonstrate the backtracking approach or an iterative DFS over graph edges.
How to solve Cracking the Safe in O(k^n)?
Model each (n-1)-length string as a node in a graph and each length-n combination as a directed edge. Run a DFS using Hierholzer's algorithm to find an Eulerian circuit that visits every edge exactly once. Append digits during traversal to construct a De Bruijn sequence that contains all combinations.
What is the best approach for Cracking the Safe?
The optimal approach uses a De Bruijn sequence constructed via Hierholzer's algorithm on a directed graph. Nodes represent (n-1)-length strings and edges represent possible password combinations. Finding an Eulerian circuit ensures every combination appears exactly once. This runs in O(k^n) time and is the standard interview solution.
Is Cracking the Safe asked at Google/Amazon/Meta?
Cracking the Safe appears in hard-level interview preparation lists and has been reported in interviews at companies like Google and Amazon. The problem tests graph modeling, Eulerian circuits, and advanced DFS traversal techniques, which are common topics in senior algorithm interviews.
What data structure is used in Cracking the Safe?
The optimal solution uses a graph representation where nodes are (n-1)-digit strings and edges represent transitions formed by appending digits. A DFS traversal with a visited-edge set or adjacency tracking is used to implement Hierholzer's algorithm for finding an Eulerian circuit.
What is the time complexity of Cracking the Safe?
The optimal graph-based solution runs in O(k^n) time because it visits each possible password combination exactly once. There are k^n edges in the De Bruijn graph, and Hierholzer's algorithm processes each edge once. Space complexity is also O(k^n) to store visited edges or combinations.

Ready to solve this problem?

Practice Cracking the Safe with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Validate Binary Search Tree