# LeetCode 753: Cracking the Safe

## Problem Restatement

We have a safe protected by an unknown password.

The password has length `n`.

Each digit can be one of:

```text
0, 1, ..., k - 1
```

When we type digits into the safe, it checks the most recent `n` digits after every key press.

For example, if the password is:

```text
345
```

and we type:

```text
012345
```

then the safe checks:

```text
012
123
234
345
```

When it sees `345`, the safe opens.

We need to return any shortest string that guarantees the safe will open, no matter which valid password was chosen.

That means the returned string must contain every possible length-`n` password as a substring.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, the password length |
| Input | `k`, the number of possible digits |
| Digits | Only digits from `0` to `k - 1` are allowed |
| Output | Any shortest string containing every length-`n` password |

Example function shape:

```python
def crackSafe(n: int, k: int) -> str:
    ...
```

## Examples

Example 1:

```python
n = 1
k = 2
```

The possible passwords are:

```text
0
1
```

A shortest answer is:

```text
01
```

Another valid shortest answer is:

```text
10
```

Both contain every password of length `1`.

Example 2:

```python
n = 2
k = 2
```

The possible passwords are:

```text
00
01
10
11
```

One valid answer is:

```text
00110
```

Its length-2 substrings are:

```text
00
01
11
10
```

So every possible password appears.

## First Thought: List Every Password

A direct idea is to write all possible passwords one after another.

For `n = 2`, `k = 2`, we could write:

```text
00 01 10 11
```

Joined together, this gives:

```text
00011011
```

This contains every password, but it is not shortest.

The problem lets neighboring passwords overlap.

For example:

```text
00
01
```

can be combined as:

```text
001
```

because `001` contains both `00` and `01`.

The goal is to overlap passwords as much as possible.

## Key Insight

We need the shortest string containing every possible length-`n` string over `k` digits.

This is exactly a de Bruijn sequence problem.

There are:

```text
k^n
```

different passwords.

Each new typed digit can introduce at most one new length-`n` substring.

So the shortest possible answer must have length:

```text
k^n + n - 1
```

The first `n` characters create the first password. Every character after that can add one new password.

So we need to build a string where every length-`n` password appears exactly once.

## Graph View

Think of each password as an edge in a graph.

Each node is a string of length `n - 1`.

For a password of length `n`, its first `n - 1` digits form the source node, and its last `n - 1` digits form the destination node.

For example, when `n = 3`, the password:

```text
012
```

becomes an edge:

```text
01 -> 12
```

The edge label is the last digit `2`.

If we walk through every edge exactly once, then we generate every password exactly once.

That is an Eulerian circuit.

## DFS Construction

We can build the answer using depth-first search.

At each node, try appending each possible digit.

The new edge is:

```python
node + digit
```

This is a length-`n` password.

If we have not used this password before, mark it used and continue DFS from the suffix of length `n - 1`.

After DFS finishes exploring from an edge, append the digit to the answer.

This postorder appending is the usual Hierholzer-style construction for an Eulerian circuit.

## Algorithm

1. Start from the node made of `n - 1` zeroes.
2. Keep a set `seen` of used length-`n` passwords.
3. Run DFS from the current node.
4. For each digit from `0` to `k - 1`:
   1. Create `edge = node + digit`.
   2. If `edge` was already used, skip it.
   3. Mark `edge` as used.
   4. Recurse into `edge[1:]`.
   5. Append `digit` to the answer.
5. After DFS, append the starting node to the end.
6. Return the built string.

## Correctness

Each edge in the graph corresponds to one possible password of length `n`.

The DFS marks an edge only when it first visits it. Therefore, no password is used more than once.

For every node, there are exactly `k` outgoing edges, one for each possible digit. The DFS tries all of them. Since the de Bruijn graph is connected in the relevant directed sense and every node has equal indegree and outdegree, an Eulerian circuit exists.

The DFS construction is Hierholzer's algorithm: it follows unused edges until they are exhausted, then appends edge labels while unwinding recursion. This produces a sequence that uses every edge exactly once.

Because every edge represents one password, the final string contains every possible password exactly once as a length-`n` substring.

There are `k^n` passwords. The returned string has length `k^n + n - 1`, which is the minimum possible length, since a string of length `L` has only `L - n + 1` substrings of length `n`.

So the algorithm returns a valid shortest string.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(k^n)` | There are `k^n` possible passwords, and each is visited once |
| Space | `O(k^n)` | The `seen` set and answer store all generated edges |

The recursion depth can also be `O(k^n)` in the worst case.

## Implementation

```python
class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        start = "0" * (n - 1)
        seen = set()
        ans = []

        def dfs(node: str) -> None:
            for digit in map(str, range(k)):
                edge = node + digit

                if edge in seen:
                    continue

                seen.add(edge)
                dfs(edge[1:])
                ans.append(digit)

        dfs(start)

        return "".join(ans) + start
```

## Code Explanation

We start with:

```python
start = "0" * (n - 1)
```

This is the initial graph node.

If `n = 3`, then `start` is:

```text
00
```

The set `seen` stores used passwords:

```python
seen = set()
```

Each item in `seen` has length `n`.

For example, when `n = 3`, possible edges include:

```text
000
001
010
999
```

The answer list stores digits in postorder:

```python
ans = []
```

Inside DFS, we try every possible next digit:

```python
for digit in map(str, range(k)):
```

The edge is the current node plus that digit:

```python
edge = node + digit
```

This edge is one full password of length `n`.

If we already used it, we skip it:

```python
if edge in seen:
    continue
```

Otherwise, we mark it:

```python
seen.add(edge)
```

Then we move to the next node:

```python
dfs(edge[1:])
```

For example, if `edge = "012"`, the next node is:

```text
12
```

After finishing that path, we append the digit:

```python
ans.append(digit)
```

Finally:

```python
return "".join(ans) + start
```

The extra `start` completes the sequence so all length-`n` windows are present.

## Testing

```python
def check_answer(ans: str, n: int, k: int) -> bool:
    expected_count = k ** n

    if len(ans) != expected_count + n - 1:
        return False

    seen = set()

    for i in range(len(ans) - n + 1):
        part = ans[i:i + n]

        if len(part) != n:
            return False

        for ch in part:
            if ch < "0" or ch >= str(k):
                return False

        seen.add(part)

    return len(seen) == expected_count

def run_tests():
    s = Solution()

    ans = s.crackSafe(1, 2)
    assert check_answer(ans, 1, 2)

    ans = s.crackSafe(2, 2)
    assert check_answer(ans, 2, 2)

    ans = s.crackSafe(2, 3)
    assert check_answer(ans, 2, 3)

    ans = s.crackSafe(3, 2)
    assert check_answer(ans, 3, 2)

    ans = s.crackSafe(1, 1)
    assert check_answer(ans, 1, 1)

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1, k = 2` | Smallest multi-digit alphabet case |
| `n = 2, k = 2` | Classic binary de Bruijn case |
| `n = 2, k = 3` | More than two digits |
| `n = 3, k = 2` | Longer password length |
| `n = 1, k = 1` | Single possible password |