Cracking the Safe
Problem
Given integers n and k, return a shortest string s of digits 0..k-1 such that every length-n combination appears at least once as a contiguous substring of s.
n=2, k=2"01100"def crackSafe(n, k):
visited = set()
res = []
def dfs(node):
for x in range(k):
nxt = node + str(x)
if nxt not in visited:
visited.add(nxt)
dfs(nxt[1:])
res.append(str(x))
start = '0' * (n - 1)
dfs(start)
return ''.join(res) + startfunction crackSafe(n, k) {
const visited = new Set();
const res = [];
function dfs(node) {
for (let x = 0; x < k; x++) {
const nxt = node + x;
if (!visited.has(nxt)) {
visited.add(nxt);
dfs(nxt.slice(1));
res.push(String(x));
}
}
}
const start = '0'.repeat(n - 1);
dfs(start);
return res.join('') + start;
}class Solution {
Set<String> visited = new HashSet<>(); StringBuilder res = new StringBuilder(); int K;
public String crackSafe(int n, int k) {
K = k;
String start = "0".repeat(n - 1);
dfs(start);
return res.toString() + start;
}
void dfs(String node) {
for (int x = 0; x < K; x++) {
String nxt = node + x;
if (!visited.contains(nxt)) {
visited.add(nxt);
dfs(nxt.substring(1));
res.append(x);
}
}
}
}class Solution {
unordered_set<string> visited; string res; int K;
public:
string crackSafe(int n, int k) {
K = k;
string start(n - 1, '0');
dfs(start);
return res + start;
}
void dfs(const string& node) {
for (int x = 0; x < K; x++) {
string nxt = node + char('0' + x);
if (!visited.count(nxt)) {
visited.insert(nxt);
dfs(nxt.substr(1));
res.push_back('0' + x);
}
}
}
};Explanation
We want one short string that contains every length-n combination of digits 0..k-1 as a substring. The neat result is that such a shortest string (a de Bruijn sequence) can be built greedily with a DFS.
Think of each window of n-1 digits as a state. Adding one more digit x forms a length-n combination node + x and moves us to a new n-1-digit state nxt[1:]. The DFS tries every digit from each state, but only follows a combination it hasn't visited yet, marking it so it's never reused.
The key trick is when we append the digit to the answer: after the recursive call returns (post-order). This is Hierholzer's idea for walking an Euler circuit — by recording digits on the way back out, every edge (combination) ends up covered with no waste.
At the end we tack on the starting prefix of n-1 zeros so the very first combinations are also represented.
Example: n = 2, k = 2. Starting from "0", the DFS uses combinations 00, 01, 11, 10 and, appending on the way back plus the prefix, produces something like "01100", in which all four pairs 00, 01, 10, 11 appear.