# Cracking the Safe
**Difficulty:** HARD
[External](https://leetcode.com/problems/cracking-the-safe)
Canonical: https://scaleengineer.com/dsa/problems/cracking-the-safe
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Eulerian Circuit](https://scaleengineer.com/algorithms/eulerian-circuit)
**Data structures:** Graph
---
## Problem
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`

# Approaches
## Backtracking Search
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    private int totalPasswords;
    private int n;
    private int k;
    private Set<String> visited;
    private StringBuilder result;

    public String crackSafe(int n, int k) {
        this.n = n;
        this.k = k;
        this.totalPasswords = (int) Math.pow(k, n);
        this.visited = new HashSet<>();
        this.result = new StringBuilder();

        for (int i = 0; i < n; i++) {
            result.append('0');
        }
        visited.add(result.toString());

        if (dfs()) {
            return result.toString();
        }
        return ""; // Should not be reached
    }

    private boolean dfs() {
        if (visited.size() == totalPasswords) {
            return true;
        }

        String prefix = result.substring(result.length() - n + 1);
        for (int i = 0; i < k; i++) {
            String password = prefix + i;
            if (!visited.contains(password)) {
                visited.add(password);
                result.append(i);
                if (dfs()) {
                    return true;
                }
                // Backtrack
                visited.remove(password);
                result.deleteCharAt(result.length() - 1);
            }
        }
        return false;
    }
}
```
### 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.

## De Bruijn Graph with Post-Order DFS
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    private Set<String> visited;
    private StringBuilder result;
    private int k;

    public String crackSafe(int n, int k) {
        if (n == 1 && k == 1) return "0";
        this.k = k;
        this.visited = new HashSet<>();
        this.result = new StringBuilder();

        StringBuilder startNodeBuilder = new StringBuilder();
        for (int i = 0; i < n - 1; i++) {
            startNodeBuilder.append('0');
        }
        String startNode = startNodeBuilder.toString();

        dfs(startNode);

        result.append(startNode);
        return result.reverse().toString();
    }

    private void dfs(String node) {
        for (int i = 0; i < k; i++) {
            String password = node + i;
            if (!visited.contains(password)) {
                visited.add(password);
                dfs(password.substring(1));
                result.append(i);
            }
        }
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
private
  Set<Integer> vis = new HashSet<>();
private
  StringBuilder ans = new StringBuilder();
private
  int mod;
public
  String crackSafe(int n, int k) {
    mod = (int)Math.pow(10, n - 1);
    dfs(0, k);
    ans.append("0".repeat(n - 1));
    return ans.toString();
  }
private
  void dfs(int u, int k) {
    for (int x = 0; x < k; ++x) {
      int e = u * 10 + x;
      if (vis.add(e)) {
        int v = e % mod;
        dfs(v, k);
        ans.append(x);
      }
    }
  }
}

```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class Solution:
    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)

```