Cracking the Safe - Video Solutions

Problem Overview: You need to generate the shortest possible string that guarantees opening a safe with an unknown password of length n, where each digit ranges from 0 to k-1. The string must contain every possible combination of length n exactly once as a substring. This is fundamentally a sequence generation problem that maps directly to graph traversal.

Approach 1: Backtracking with Visited Combinations (Time: O(k^n * n), Space: O(k^n))

This approach builds the sequence incrementally using Depth-First Search. Start with a prefix of n zeros, then repeatedly append digits from 0 to k-1. Each time you append a digit, form the last n-length substring and mark it as visited. If that combination hasn’t appeared before, continue the DFS. When all k^n combinations are visited, the constructed string is valid. Backtracking removes the last digit if a branch cannot cover all combinations. This method is conceptually simple and mirrors typical DFS permutation generation, but it becomes expensive as n grows because each recursive step checks and tracks visited states.

Approach 2: De Bruijn Sequence using Hierholzer's Algorithm (Time: O(k^n), Space: O(k^n))

The optimal solution models the problem as an graph. Each node represents a string of length n-1. Each directed edge represents appending a digit (forming a length n combination). Since every combination must appear exactly once, the task becomes finding an Eulerian circuit that visits every edge exactly once. Hierholzer’s algorithm performs a DFS traversal that consumes edges as they are visited. When traversing from node u, append digits 0..k-1, mark edges as used, and recursively explore the next node formed by the last n-1 characters. The resulting traversal naturally constructs a De Bruijn sequence. After DFS finishes, append the initial n-1 prefix to complete the cycle.

The key insight is that each edge corresponds to a unique password combination, so covering all edges exactly once ensures every possible password appears in the sequence. Instead of brute-forcing combinations, the algorithm systematically walks the graph structure that represents them.

Recommended for interviews: Interviewers usually expect the De Bruijn sequence solution with Hierholzer’s algorithm. It shows you recognize the transformation from substring coverage to Eulerian traversal. Explaining the backtracking version first demonstrates understanding of the search space, but implementing the graph-based approach proves stronger algorithmic maturity.