Cracking the Safe

HardGraphs · Eulerian Circuit (Hierholzer) · De Bruijn🧩 MST & Euler Paths LeetCode #753 ↗Updated Oct 30, 2026

Problem

A safe's password is n digits long, each digit in 0..k-1. The safe checks the last n digits typed after every keystroke and opens when they match. Return any shortest string that is guaranteed to open the safe, i.e. one that contains every possible n-digit password as a substring.

Inputn=1, k=2Output"10" (or "01")

Inputn=2, k=2Output"01100" (any valid answer, e.g. "00110")

1 ≤ n ≤ 4 · 1 ≤ k ≤ 10 · 1 ≤ kⁿ ≤ 4096 · minimum length is kⁿ + n − 1

Try it yourself

Java

class Solution {
    public String crackSafe(int n, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Make every (n-1)-digit string a node and every n-digit password an edge (prefix → suffix). Each node has equal in- and out-degree k, so an Eulerian circuit exists; walking it uses each password exactly once, giving the minimal length kⁿ + n − 1.

PatternMST & Euler Paths

Instinct "Connect every point for the least total cost" means a minimum spanning tree; "use every edge or ticket exactly once" means an Euler path.

Memory hack MST - grab the cheapest bridge that joins two separate islands. Euler - wander until stuck, write the stop down on the way back, then reverse.

Open the MST & Euler Paths guide →

Approaches

Brute ForceBacktracking over Passwords (Hamiltonian Search)

Time Exponential worst caseSpace O(n · kⁿ)

Start with n zeros. Repeatedly try appending a digit whose new last-n window is unseen; recurse, and undo if the branch gets stuck before all kⁿ windows are seen. This is a Hamiltonian-path search over passwords.

Java

private int total;

public String crackSafe(int n, int k) {
    total = (int) Math.pow(k, n);
    StringBuilder sb = new StringBuilder("0".repeat(n));
    Set<String> seen = new HashSet<>();
    seen.add(sb.toString());
    dfs(sb, seen, n, k);
    return sb.toString();
}

private boolean dfs(StringBuilder sb, Set<String> seen, int n, int k) {
    if (seen.size() == total) return true;
    String tail = sb.substring(sb.length() - n + 1); // last n-1 digits
    for (int d = 0; d < k; d++) {
        String window = tail + d;
        if (seen.contains(window)) continue;
        seen.add(window);
        sb.append(d);
        if (dfs(sb, seen, n, k)) return true;
        seen.remove(window); // undo and try the next digit
        sb.setLength(sb.length() - 1);
    }
    return false;
}

Finds an answer quickly here in practice, but nothing bounds the backtracking.

BetterGreedy “Prefer the Largest Digit”

Time O(kⁿ · k)Space O(kⁿ)

Start with n zeros and always append the largest digit whose window has not appeared yet. A classical de Bruijn theorem guarantees this greedy never gets stuck early, so no backtracking is needed. Windows are encoded as base- k integers for O(1) checks.

Java

public String crackSafe(int n, int k) {
    int total = (int) Math.pow(k, n);
    boolean[] seen = new boolean[total];
    StringBuilder sb = new StringBuilder("0".repeat(n));
    seen[0] = true;
    int window = 0; // current last-n digits as a base-k number
    for (int added = 1; added < total; added++) {
        int base = (window * k) % total; // drop the oldest digit, shift left
        for (int d = k - 1; d >= 0; d--) {
            if (!seen[base + d]) {
                seen[base + d] = true;
                window = base + d;
                sb.append(d);
                break;
            }
        }
    }
    return sb.toString();
}

Tiny and fast, but its correctness rests on a theorem that is hard to derive live.

OptimalHierholzer's Eulerian Circuit on the De Bruijn Graph

Time O(kⁿ)Space O(kⁿ)

Nodes are (n-1)-digit values; from node u, digit d is the edge u·k + d leading to (u·k + d) mod k^n-1. Hierholzer's DFS uses every edge once and emits digits in post-order; reversing them and prefixing the start node spells the circuit.

Java

private boolean[] used;
private int mod, k;
private StringBuilder digits;

public String crackSafe(int n, int k) {
    this.k = k;
    mod = (int) Math.pow(k, n - 1); // number of (n-1)-digit nodes
    used = new boolean[mod * k];    // one edge per n-digit password
    digits = new StringBuilder();
    dfs(0);
    // Post-order is the circuit backwards; prefix the start node 0...0
    return "0".repeat(n - 1) + digits.reverse();
}

private void dfs(int node) {
    for (int d = 0; d < k; d++) {
        int edge = node * k + d;
        if (used[edge]) continue;
        used[edge] = true;
        dfs(edge % mod);
        digits.append(d);
    }
}

Each of the kⁿ edges is visited once, with a textbook correctness proof.

Pro tip

Edge u·k + d is literally the n-digit password; taking it modulo k^n-1 drops its first digit to get the next node.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking over Passwords (Hamiltonian Search)	`Exponential worst case`	`O(n · kⁿ)`
Better	Greedy “Prefer the Largest Digit”	`O(kⁿ · k)`	`O(kⁿ)`
Optimal	Hierholzer's Eulerian Circuit on the De Bruijn Graph	`O(kⁿ)`	`O(kⁿ)`

Common pitfalls

Modelling passwords as nodes — that needs a Hamiltonian path (hard); make them edges.
Forgetting the n−1 starting digits — the answer is kⁿ+n−1 long.
Handling n = 1: there are no prefix digits and a single node with k self-loops.

Interview tips

Explain why each node has in = out = k, which guarantees an Eulerian circuit.
State the lower bound: each new character can add at most one new window.
Mention the iterative stack form of Hierholzer if recursion depth is a concern.

Pattern

Eulerian path / de Bruijn → build the shortest sequence that covers every overlapping item exactly once.

My notes saved in this browser