Cracking the Safe

Hard

#0707Time: `O(n * k^n)`. The search space is a graph with `k^n` edges. The DFS will traverse each edge once. At each step, creating the new password string and performing set operations takes `O(n)` time.Space: `O(n * k^n)`. This is dominated by the `visited` set which stores `k^n` passwords of length `n`. The recursion stack can also go as deep as `k^n`.

Algorithms

Depth-First Search Eulerian Circuit

Data structures

Graph

Prompt

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 <= kⁿ <= 4096

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves building the result string incrementally using a backtracking algorithm. We start with an initial password (e.g., n zeros). Then, we try to extend this string one character at a time. At each step, we consider appending each possible digit. If appending a digit creates a new, unseen password, we make that move and continue the search recursively. If we hit a dead end or a path that doesn't lead to a full solution, we backtrack by undoing the last move. This process continues until we have generated a string that contains all k^n possible passwords.

Algorithm

Use a HashSet<String> to keep track of all the unique n-digit passwords we have formed so far.
Use a StringBuilder to construct our candidate superstring.
Start by initializing the StringBuilder with n zeros and adding this initial password to our set of visited passwords.
The core of the algorithm is a recursive dfs function that returns true upon finding a complete solution.
In dfs, first check if the size of our visited set equals k^n. If it does, we have found all passwords, and the search is complete, so we return true.
If not, take the last n-1 characters from our StringBuilder. This forms the prefix for the next potential password.
Loop through all possible digits d. Append d to the prefix to form a newPassword.
If newPassword is not in our visited set, it's a valid next move. Add newPassword to the set, append d to our StringBuilder, and make a recursive call to dfs.
If the recursive call returns true, it means a solution was found down that path, so we propagate true up the call stack.
If the recursive call returns false, we must backtrack. We remove newPassword from the visited set and delete the last character d from our StringBuilder to explore other possibilities.
Since a solution is always possible, this search is guaranteed to find a valid string.

Walkthrough

We use a HashSet<String> to keep track of all the unique n-digit passwords we have formed so far and a StringBuilder to construct our candidate superstring. We start by initializing the StringBuilder with n zeros and adding this initial password to our set of visited passwords. The core of the algorithm is a recursive dfs function that returns true upon finding a complete solution. In dfs, we first check if the size of our visited set equals k^n. If it does, we have found all passwords, and the search is complete, so we return true. If not, we take the last n-1 characters from our StringBuilder to form the prefix for the next potential password. We then loop through all possible digits d, appending d to the prefix to form a newPassword. If newPassword is not in our visited set, it's a valid next move. We add newPassword to the set, append d to our StringBuilder, and make a recursive call to dfs. If the recursive call returns true, it means a solution was found down that path, so we propagate true up the call stack. If the recursive call returns false, we must backtrack by removing newPassword from the visited set and deleting the last character d from our StringBuilder to explore other possibilities. Since a solution is always possible, this search is guaranteed to find a valid string.

1class Solution {2    private int totalPasswords;3    private int n;4    private int k;5    private Set<String> visited;6    private StringBuilder result;7 8    public String crackSafe(int n, int k) {9        this.n = n;10        this.k = k;11        this.totalPasswords = (int) Math.pow(k, n);12        this.visited = new HashSet<>();13        this.result = new StringBuilder();14 15        for (int i = 0; i < n; i++) {16            result.append('0');17        }18        visited.add(result.toString());19 20        if (dfs()) {21            return result.toString();22        }23        return ""; // Should not be reached24    }25 26    private boolean dfs() {27        if (visited.size() == totalPasswords) {28            return true;29        }30 31        String prefix = result.substring(result.length() - n + 1);32        for (int i = 0; i < k; i++) {33            String password = prefix + i;34            if (!visited.contains(password)) {35                visited.add(password);36                result.append(i);37                if (dfs()) {38                    return true;39                }40                // Backtrack41                visited.remove(password);42                result.deleteCharAt(result.length() - 1);43            }44        }45        return false;46    }47}

Complexity

Time

`O(n * k^n)`. The search space is a graph with `k^n` edges. The DFS will traverse each edge once. At each step, creating the new password string and performing set operations takes `O(n)` time.

Space

`O(n * k^n)`. This is dominated by the `visited` set which stores `k^n` passwords of length `n`. The recursion stack can also go as deep as `k^n`.

Trade-offs

Pros

It's a direct and intuitive application of backtracking for this type of construction problem.

Cons

The repeated modification of the result StringBuilder (append and delete) can be slightly less efficient than a single final construction.
The deep recursion can potentially lead to a StackOverflowError for the maximum possible k^n (4096), although it's often fine in practice.

This is a more elegant and standard approach that frames the problem in terms of graph theory. We can model the problem as finding an Eulerian path in a De Bruijn graph. The nodes of this graph are all possible prefixes of length n-1, and the directed edges represent appending a digit to form a password of length n. Since this graph is guaranteed to have an Eulerian path (a path that visits every edge exactly once), our goal is to find it. The sequence of digits appended along this path, when combined with the starting prefix, gives the shortest superstring. Hierholzer's algorithm, commonly implemented with a post-order DFS, is perfect for this task.

Algorithm

Model the problem as a graph where nodes are prefixes of length n-1 and edges are the k possible digits to append.
Use a Set<String> to keep track of visited edges (which are the full passwords of length n).
Use a StringBuilder to build the sequence of appended digits.
Implement a post-order DFS function dfs(String node).
Inside dfs(node), loop through all possible next digits d.
For each d, form the edge (password) p = node + d.
If p has not been visited, mark it as visited and recursively call dfs on the destination node, which is p.substring(1).
After the recursive call for a given d returns, append d to the result StringBuilder. This is the "post-order" step.
Start the process by calling dfs on an initial node, typically n-1 zeros.
After the initial dfs call completes, the StringBuilder will contain the k^n digits that form the path, but in reverse order.
The final string is the starting node concatenated with the reversed StringBuilder.

Walkthrough

The algorithm explores the implicit graph of prefixes. A node is a string of n-1 digits. An edge from node u is formed by appending a digit d, creating a password u+d. The destination node of this edge is the last n-1 characters of the password, i.e., (u+d).substring(1). We use a Set<String> to keep track of visited edges (passwords) and a StringBuilder to build the final sequence of appended digits. The algorithm is a recursive DFS function, dfs(String node). Inside dfs(node), we loop through all possible next digits d. For each d, we form the edge (password) p = node + d. If p has not been visited, we mark it as visited and recursively call dfs on the destination node, which is p.substring(1). Crucially, after the recursive call for a given d returns, we append d to our result StringBuilder. This is the "post-order" step. It ensures that a digit is added to the result only after the entire path starting from its corresponding edge has been fully explored. We start the process by calling dfs on an initial node, typically n-1 zeros. After the initial dfs call completes, the StringBuilder will contain the k^n digits that form the path, but in reverse order of traversal. The final result is constructed by taking the starting node (the initial n-1 zeros), appending it to the StringBuilder, and then reversing the whole thing.

1class Solution {2    private Set<String> visited;3    private StringBuilder result;4    private int k;5 6    public String crackSafe(int n, int k) {7        if (n == 1 && k == 1) return "0";8        this.k = k;9        this.visited = new HashSet<>();10        this.result = new StringBuilder();11 12        StringBuilder startNodeBuilder = new StringBuilder();13        for (int i = 0; i < n - 1; i++) {14            startNodeBuilder.append('0');15        }16        String startNode = startNodeBuilder.toString();17 18        dfs(startNode);19 20        result.append(startNode);21        return result.reverse().toString();22    }23 24    private void dfs(String node) {25        for (int i = 0; i < k; i++) {26            String password = node + i;27            if (!visited.contains(password)) {28                visited.add(password);29                dfs(password.substring(1));30                result.append(i);31            }32        }33    }34}

Complexity

Time

`O(n * k^n)`. The algorithm visits each of the `k^n` edges of the De Bruijn graph exactly once. The work done per edge involves string manipulations and set operations, taking `O(n)` time.

Space

`O(n * k^n)`. The space is dominated by the `visited` set, which stores `k^n` passwords of length `n`, and the recursion stack, which can reach a depth of `k^n`.

Trade-offs

Pros

It's an elegant and efficient algorithm based on a solid mathematical foundation (De Bruijn sequences).
The result string is constructed once at the end, which can be more efficient than repeated modifications.

Cons

The logic of post-order traversal and final string construction can be less intuitive than a direct backtracking approach.
Like the backtracking approach, it uses a recursive implementation that could face stack depth limits, although an iterative version using an explicit stack is also possible.

Solutions

Solution

1class Solution {2private3  Set<Integer> vis = new HashSet<>();4private5  StringBuilder ans = new StringBuilder();6private7  int mod;8public9  String crackSafe(int n, int k) {10    mod = (int)Math.pow(10, n - 1);11    dfs(0, k);12    ans.append("0".repeat(n - 1));13    return ans.toString();14  }15private16  void dfs(int u, int k) {17    for (int x = 0; x < k; ++x) {18      int e = u * 10 + x;19      if (vis.add(e)) {20        int v = e % mod;21        dfs(v, k);22        ans.append(x);23      }24    }25  }26}

1class Solution { public: string crackSafe ( int n , int k ) { unordered_set < int > vis ; int mod = pow ( 10 , n - 1 ); string ans ; function < void ( int ) > dfs = [ & ]( int u ) { for ( int x = 0 ; x < k ; ++ x ) { int e = u * 10 + x ; if ( ! vis . count ( e )) { vis . insert ( e ); dfs ( e % mod ); ans += ( x + '0' ); } } }; dfs ( 0 ); ans += string ( n - 1 , '0' ); return ans ; } };

1class Solution:2    def crackSafe(self, n: int, k: int) -> str: def dfs(u): for x in range(k): e = u * 10 + x if e not in vis: vis . add(e) v = e % mod dfs(v) ans . append(str(x)) mod = 10 ** (n - 1) vis = set() ans = [] dfs(0) ans . append("0" * (n - 1)) return "" . join(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem