DSA problem
Cracking the Safe
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: it only checks the most recent n digits entered. For example, assuming the real password is "345", if you enter "012345", it would accept the password because the last n digits "345" match. Return any string of minimum length that will unlock the safe at some point of entering it.
The answer length is exactly k^n + (n - 1). Every length-n string over the alphabet must appear as a contiguous window somewhere in the output, so the output cannot be shorter than the number of distinct windows plus the overlap that the first window uses. Such a string is called a de Bruijn sequence B(k, n).
The classical construction reduces the problem to finding an Eulerian circuit on a carefully chosen directed graph. Build a graph whose vertices are the k^(n-1) strings of length n - 1 over the alphabet. From each vertex u add k outgoing edges, one per digit d in [0, k), going to the vertex obtained by dropping the first character of u and appending d. Each such edge corresponds to a unique length-n window — the concatenation of u and d — so traversing every edge exactly once covers every window exactly once.
The graph is Eulerian (every vertex has equal in- and out-degree k), so an Eulerian circuit exists. Run Hierholzer's algorithm starting from the all-zero vertex: DFS that consumes edges and pushes a digit to the result whenever an edge is fully exhausted. The output is the starting vertex's n - 1 digits followed by the reverse of the edge-emission sequence, giving the minimum-length de Bruijn-like password in O(k^n) time and space.
Examples
n = 1, k = 2"10"n = 2, k = 2"01100"n = 2, k = 3"002210110"Constraints
- 1 <= n <= 4
- 1 <= k <= 10
- 1 <= k^n <= 4096
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.