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:

1
2
3
4
5


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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);
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


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.

Problem#

Examples#

Solution#

Method 1 – DFS and De Bruijn Sequence Construction#

Intuition#

Approach#

Code#

Complexity#