LeetCode 753 - Cracking the Safe

LeetCode Problem 753

Difficulty: 🔴 Hard
Topics: String, Depth-First Search, Graph Theory, Eulerian Circuit

Solution

Problem Understanding

This problem asks us to generate the shortest possible string that guarantees a safe will unlock at some point while typing it.

The safe password has exactly n digits, and each digit can be any value from 0 to k - 1. The safe does not validate the entire entered sequence at once. Instead, after every digit typed, it checks the most recent n digits to see if they match the password.

Our goal is to construct a string such that every possible password of length n appears somewhere as a contiguous substring exactly once or at least once. Since the safe unlocks the moment the correct password appears among the most recent n digits, including every possible password guarantees success.

The challenge is to make this sequence as short as possible.

For example, if n = 2 and k = 2, the possible passwords are:

• "00"
• "01"
• "10"
• "11"

A naive solution might concatenate all of them:

00011011

However, this repeats many digits unnecessarily. Since overlapping is allowed, we can reuse suffixes and prefixes to compress the sequence:

01100

This contains every possible 2-digit password exactly once as a substring.

The constraints provide an important clue:

• 1 <= n <= 4
• 1 <= k <= 10
• k^n <= 4096

The maximum number of possible passwords is at most 4096, which strongly suggests a graph traversal approach is feasible.

An important observation is that we must include all k^n possible length-n combinations, otherwise some password might never appear and the safe would fail to unlock.

Several edge cases are important:

• n = 1, where every digit itself is a password.
• k = 1, where only one digit exists (0), meaning only one password is possible regardless of n.
• Small values where overlap must be handled carefully to avoid duplicate states.
• Cases where revisiting nodes could create cycles and infinite recursion if not tracked properly.

Approaches

Brute Force Approach

A brute-force solution would attempt to generate strings incrementally and check whether every possible password of length n appears.

We could repeatedly append digits and track which n-length substrings have been seen. At every step, we would try all possible next digits and backtrack until every combination appears.

This works because eventually, an exhaustive search will find a valid sequence. However, the search space grows explosively. Every position can choose among k digits, and many partial strings lead to redundant states.

The core issue is that brute force does not exploit the overlap between passwords. Since neighboring passwords may share n - 1 digits, recomputing equivalent states becomes prohibitively expensive.

Key Insight

This problem is actually asking us to construct a minimum-length sequence containing every possible length-n combination exactly once as a substring.

This is a classic De Bruijn sequence problem.

We can model the problem as a graph:

• Each node represents an (n - 1)-digit sequence.
• Each edge represents appending a digit, producing an n-digit password.

For example, with n = 2 and k = 2:

Nodes:

0, 1

Edges:

0 -> 0  (00)
0 -> 1  (01)
1 -> 0  (10)
1 -> 1  (11)

Since every node has equal in-degree and out-degree, this forms an Eulerian graph.

The optimal sequence corresponds to an Eulerian circuit, meaning we traverse every edge exactly once. Each edge represents one password, so visiting all edges ensures every password appears exactly once.

We can build the answer using Hierholzer’s algorithm with Depth-First Search (DFS).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^(k^n))	O(k^n)	Exhaustive search over possible sequences
Optimal	O(k^n)	O(k^n)	Eulerian circuit on De Bruijn graph

Algorithm Walkthrough

Optimal Algorithm, Eulerian Circuit via DFS

1. Handle the graph representation implicitly

Instead of explicitly constructing a graph, we represent nodes as strings of length n - 1.

A node corresponds to the suffix currently available for extension.

For example, if n = 3 and current node is "01", appending digit "2" forms password "012". 2. Start from the all-zero node

We begin at:

"0" * (n - 1)

This serves as the starting node in the Eulerian traversal. 3. Track visited edges

Since edges represent passwords, we must ensure each password is used exactly once.

We store visited passwords in a hash set:

visited = {password_strings}

Example:

"00", "01", "10", "11"

4. Perform DFS using Hierholzer’s algorithm

At each node:

• Try appending every digit from 0 to k - 1
• Form the new edge:

next_password = node + digit

If this edge has not been visited:

• Mark it visited
• Recurse on the suffix:

next_password[1:]

This keeps only the last n - 1 digits. 5. Append digits during backtracking

The crucial insight of Hierholzer’s algorithm is that we append digits after recursion, not before.

This guarantees the Eulerian ordering is built correctly.

When recursion returns:

answer.append(digit)

6. Append the starting prefix

Since nodes only store n - 1 digits, we must append:

"0" * (n - 1)

at the end to complete the sequence. 7. Return the final string

Join all collected digits into the answer.

Why it works

The graph contains exactly one edge for every possible password of length n. Hierholzer’s algorithm guarantees every edge is traversed exactly once in an Eulerian circuit. Since every edge corresponds to a unique password, every possible password appears exactly once as a substring in the resulting sequence.

Because overlapping is maximized through graph traversal, the resulting string has minimum length:

k^n + n - 1

which is provably optimal.

Python Solution

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        start = "0" * (n - 1)
        visited: set[str] = set()
        sequence: list[str] = []

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

                if edge not in visited:
                    visited.add(edge)
                    dfs(edge[1:])
                    sequence.append(digit)

        dfs(start)

        return "".join(sequence) + start

Implementation Explanation

We begin by defining the starting node as n - 1 zeros. This represents the initial graph state.

The visited set stores edges rather than nodes. This distinction is important because passwords correspond to edges in the graph, not vertices. Visiting a node multiple times is allowed, but each password must appear exactly once.

The DFS function implements Hierholzer’s algorithm. For every possible digit, we create a candidate edge by appending the digit to the current node. If the edge has not been visited, we recurse into the suffix state.

The most subtle part of the implementation is appending digits during backtracking. This reverse construction ensures the Eulerian traversal is produced correctly.

Finally, we append the starting prefix to reconstruct the full sequence.

Go Solution

func crackSafe(n int, k int) string {
	start := ""
	for i := 0; i < n-1; i++ {
		start += "0"
	}

	visited := make(map[string]bool)
	var sequence []byte

	var dfs func(string)
	dfs = func(node string) {
		for digit := 0; digit < k; digit++ {
			edge := node + string(rune('0'+digit))

			if !visited[edge] {
				visited[edge] = true
				dfs(edge[1:])
				sequence = append(sequence, byte('0'+digit))
			}
		}
	}

	dfs(start)

	return string(sequence) + start
}

Go-Specific Notes

The Go implementation mirrors the Python solution closely.

A map[string]bool is used instead of a Python set for visited edges. The sequence is stored as a []byte for efficient appending and conversion into a string.

Digit conversion is handled using:

string(rune('0' + digit))

Since k <= 10, digits remain within '0' to '9', so character arithmetic is safe.

Go slices are mutable and efficient for incremental appending, making []byte a natural choice for constructing the result.

Worked Examples

Example 1

n = 1, k = 2

Possible passwords:

0, 1

Initial state:

start = ""
visited = {}
sequence = []

Step	Node	Edge	Action	Sequence
1	""	"0"	Visit	[]
2	""	"1"	Visit	[]
3	Backtrack	"1"	Append 1	[1]
4	Backtrack	"0"	Append 0	[1,0]

Final result:

"10"

This contains:

1
0

Both passwords appear.

Example 2

n = 2, k = 2

Possible passwords:

00, 01, 10, 11

Initial state:

start = "0"

Traversal:

Step	Node	Edge	Visited
1	0	00	yes
2	0	01	yes
3	1	10	yes
4	1	11	yes

Backtracking order appends digits:

0 → 1 → 1 → 0

Result:

01100

Substrings of length 2:

Position	Substring
1	01
2	11
3	10
4	00

Every password appears exactly once.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k^n)	Each password edge is visited exactly once
Space	O(k^n)	Visited edges plus recursion stack

The graph contains exactly k^n edges because every possible password corresponds to one edge. DFS visits each edge once, giving linear complexity in the number of passwords.

The visited set stores all passwords, requiring O(k^n) memory. The recursion depth is also bounded by the number of edges in the worst case.

Test Cases

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

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

                if edge not in visited:
                    visited.add(edge)
                    dfs(edge[1:])
                    sequence.append(digit)

        dfs(start)
        return "".join(sequence) + start

def verify(result: str, n: int, k: int) -> bool:
    passwords = {
        result[i:i+n]
        for i in range(len(result) - n + 1)
    }

    expected = {
        "".join(map(str, digits))
        for digits in __import__("itertools").product(
            range(k), repeat=n
        )
    }

    return passwords == expected

sol = Solution()

# Provided examples
assert verify(sol.crackSafe(1, 2), 1, 2)  # Example 1
assert verify(sol.crackSafe(2, 2), 2, 2)  # Example 2

# Smallest valid input
assert verify(sol.crackSafe(1, 1), 1, 1)  # Single password

# Single digit passwords
assert verify(sol.crackSafe(1, 5), 1, 5)  # All digits appear

# Only one digit available
assert verify(sol.crackSafe(4, 1), 4, 1)  # Only "0000"

# Larger overlap case
assert verify(sol.crackSafe(3, 2), 3, 2)  # Binary passwords length 3

# Maximum constraint stress case
assert verify(sol.crackSafe(4, 8), 4, 8)  # Large state space

# Verify minimum length
result = sol.crackSafe(2, 3)
assert len(result) == (3 ** 2 + 2 - 1)  # Optimal length

Test	Why
n=1, k=2	Validates provided example
n=2, k=2	Validates overlap behavior
n=1, k=1	Smallest boundary case
n=1, k=5	Ensures all digits appear
n=4, k=1	Single-character alphabet
n=3, k=2	Standard De Bruijn traversal
n=4, k=8	Stress test near upper limits
Minimum length check	Verifies optimality

Edge Cases

Case 1, n = 1

When n = 1, there is no (n - 1) suffix. The starting node becomes an empty string.

This can easily introduce bugs because substring logic like edge[1:] may seem unsafe. However, slicing works correctly and simply returns another empty string, allowing DFS to proceed normally.

For example:

n = 1, k = 2

The algorithm generates:

10

which contains both possible passwords.

Case 2, k = 1

When only one digit exists, every password must consist entirely of zeros.

For example:

n = 4, k = 1

The only valid password is:

0000

A buggy implementation might recurse infinitely because every transition looks identical. The visited edge set prevents revisiting the same password.

Case 3, Duplicate Password Generation

A common bug is tracking visited nodes instead of visited edges.

In Eulerian traversal, nodes may be revisited many times. What matters is that each password appears exactly once.

For example:

n = 2, k = 2

Node "0" must be revisited to generate both:

00
01

Tracking only nodes would incorrectly skip valid passwords and produce an incomplete sequence. By tracking edges, the implementation guarantees correctness.