LeetCode 753: Cracking the Safe

A clear explanation of Cracking the Safe using a de Bruijn sequence and depth-first search over password states.

leetcodedfsgrapheulerian-pathde-bruijn-sequence

Problem Restatement

We have a safe protected by an unknown password.

The password has length n.

Each digit can be one of:

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:

345

and we type:

012345

then the safe checks:

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:

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

Examples

Example 1:

n = 1
k = 2

The possible passwords are:

0
1

A shortest answer is:

01

Another valid shortest answer is:

10

Both contain every password of length 1.

Example 2:

n = 2
k = 2

The possible passwords are:

00
01
10
11

One valid answer is:

00110

Its length-2 substrings are:

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:

00 01 10 11

Joined together, this gives:

00011011

This contains every password, but it is not shortest.

The problem lets neighboring passwords overlap.

For example:

00
01

can be combined as:

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:

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:

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:

012

becomes an edge:

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:

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

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:

start = "0" * (n - 1)

This is the initial graph node.

If n = 3, then start is:

00

The set seen stores used passwords:

seen = set()

Each item in seen has length n.

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

000
001
010
999

The answer list stores digits in postorder:

ans = []

Inside DFS, we try every possible next digit:

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

The edge is the current node plus that digit:

edge = node + digit

This edge is one full password of length n.

If we already used it, we skip it:

if edge in seen:
    continue

Otherwise, we mark it:

seen.add(edge)

Then we move to the next node:

dfs(edge[1:])

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

12

After finishing that path, we append the digit:

ans.append(digit)

Finally:

return "".join(ans) + start

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

Testing

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