> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Cracking the Safe Python Solution with Tests

> Tested Python solution for LeetCode 753 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 753, [Hard](/catalog/hard). Topics: [String](/catalog/topics/string), [Depth-First Search](/catalog/topics/depth-first-search), [Graph Theory](/catalog/topics/graph-theory), Eulerian Circuit, Eulerian Path, Eulerian Graph. [View on LeetCode](https://leetcode.com/problems/cracking-the-safe/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 753   # by problem number
lcpy gen -s cracking_the_safe   # by problem name
```

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

### Examples

```
Input: n = 1, k = 2
Output: "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.
```

```
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^n <= 4096`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/cracking_the_safe/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/cracking_the_safe/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(k^n) - each of the k^n edges is visited exactly once
    # Space: O(k^n) - visited set plus the Eulerian path stack
    def crack_safe(self, n: int, k: int) -> str:
        if n == 1:
            return "".join(str(d) for d in range(k - 1, -1, -1))

        start = "0" * (n - 1)
        seen: set[str] = set()
        digits: list[str] = []

        def dfs(node: str) -> None:
            for d in range(k):
                edge = node + str(d)
                if edge not in seen:
                    seen.add(edge)
                    dfs(edge[1:])
                    digits.append(str(d))

        dfs(start)
        return "".join(digits) + start
```

## Complexity

| Time | Space |
| - | - |
| O(k^n) - each of the k^n edges is visited exactly once | O(k^n) - visited set plus the Eulerian path stack |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.