Cracking the Safe

Problem

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. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.

• For example, the correct password is "345" and you enter in "012345":
  • After typing 0, the most recent 3 digits is "0", which is incorrect.
  • After typing 1, the most recent 3 digits is "01", which is incorrect.
  • After typing 2, the most recent 3 digits is "012", which is incorrect.
  • After typing 3, the most recent 3 digits is "123", which is incorrect.
  • After typing 4, the most recent 3 digits is "234", which is incorrect.
  • After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.

Return any string of minimum length that will unlock the safe at some point of entering it.

Examples

Example 1:

Input:
n = 1, k = 2
Output:
 "10"
Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.

Example 2:

Input:
n = 2, k = 2
Output:
 "01100"
Explanation: For each possible password:
- "00" is typed in starting from the 4th digit.
- "01" is typed in starting from the 1st digit.
- "10" is typed in starting from the 3rd digit.
- "11" is typed in starting from the 2nd digit.
Thus "01100" will unlock the safe. "10011", and "11001" would also unlock the safe.

Solution

Method 1 – DFS and De Bruijn Sequence Construction

Intuition

The minimum string that unlocks the safe must contain every possible password of length n as a substring. This is equivalent to constructing a De Bruijn sequence of order n on k digits. We use DFS to build the sequence by visiting every possible combination exactly once.

Approach

1. Start with a string of n-1 zeros as the initial node.
2. Use DFS to explore all possible next digits, appending each digit to the sequence if the resulting substring hasn't been visited.
3. Mark each visited substring to avoid repeats.
4. After visiting all possible combinations, append the initial node to complete the sequence.
5. Return the constructed sequence.

Code

Java

class Solution {
    public String crackSafe(int n, int k) {
        StringBuilder ans = new StringBuilder();
        Set<String> vis = new HashSet<>();
        String start = "0".repeat(n - 1);
        dfs(start, n, k, vis, ans);
        ans.append(start);
        return ans.toString();
    }
    void dfs(String node, int n, int k, Set<String> vis, StringBuilder ans) {
        for (int i = 0; i < k; i++) {
            String next = node + i;
            if (!vis.contains(next)) {
                vis.add(next);
                dfs(next.substring(1), n, k, vis, ans);
                ans.append(i);
            }
        }
    }
}

C++

class Solution {
public:
    string crackSafe(int n, int k) {
        string ans;
        unordered_set<string> vis;
        string start(n - 1, '0');
        dfs(start, n, k, vis, ans);
        ans += start;
        return ans;
    }
    void dfs(string node, int n, int k, unordered_set<string>& vis, string& ans) {
        for (int i = 0; i < k; ++i) {
            string next = node + to_string(i);
            if (!vis.count(next)) {
                vis.insert(next);
                dfs(next.substr(1), n, k, vis, ans);
                ans += to_string(i);
            }
        }
    }
};

Go

func crackSafe(n int, k int) string {
    vis := map[string]bool{}
    var ans []byte
    start := make([]byte, n-1)
    for i := range start { start[i] = '0' }
    var dfs func(string)
    dfs = func(node string) {
        for i := 0; i < k; i++ {
            next := node + string('0'+i)
            if !vis[next] {
                vis[next] = true
                dfs(next[1:])
                ans = append(ans, byte('0'+i))
            }
        }
    }
    dfs(string(start))
    return string(ans) + string(start)
}

Python

class Solution:
    def crackSafe(self, n: int, k: int) -> str:
        vis = set()
        ans = []
        start = '0' * (n - 1)
        def dfs(node: str):
            for i in range(k):
                nxt = node + str(i)
                if nxt not in vis:
                    vis.add(nxt)
                    dfs(nxt[1:])
                    ans.append(str(i))
        dfs(start)
        return ''.join(ans) + start

Rust

use std::collections::HashSet;
impl Solution {
    pub fn crack_safe(n: i32, k: i32) -> String {
        let mut vis = HashSet::new();
        let mut ans = String::new();
        let start = "0".repeat((n - 1) as usize);
        fn dfs(node: &str, n: i32, k: i32, vis: &mut HashSet<String>, ans: &mut String) {
            for i in 0..k {
                let next = format!("{}{}", node, i);
                if !vis.contains(&next) {
                    vis.insert(next.clone());
                    dfs(&next[1..], n, k, vis, ans);
                    ans.push_str(&i.to_string());
                }
            }
        }
        dfs(&start, n, k, &mut vis, &mut ans);
        ans.push_str(&start);
        ans
    }
}

TypeScript

class Solution {
    crackSafe(n: number, k: number): string {
        const vis = new Set<string>();
        let ans = '';
        const start = '0'.repeat(n - 1);
        function dfs(node: string) {
            for (let i = 0; i < k; i++) {
                const next = node + i;
                if (!vis.has(next)) {
                    vis.add(next);
                    dfs(next.slice(1));
                    ans += i;
                }
            }
        }
        dfs(start);
        return ans + start;
    }
}

Complexity

• ⏰ Time complexity: O(k^n), since there are k^n possible passwords and each is visited once.
• 🧺 Space complexity: O(k^n), for the visited set and recursion stack.