Last updated on March 2nd, 2025 at 02:55 pm

Here, we see a Cracking the Safe LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth-First Search

Level of Question

Hard

Cracking the Safe LeetCode Solution

1. Problem Statement

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.

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 4^th digit. – “01” is typed in starting from the 1^st digit. – “10” is typed in starting from the 3^rd digit. – “11” is typed in starting from the 2^nd digit. Thus “01100” will unlock the safe. “10011”, and “11001” would also unlock the safe.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Eulerian Path/De Bruijn Sequence Construction. The problem involves finding a sequence that visits every possible combination of digits of length n exactly once, which is a classic application of constructing a De Bruijn sequence using a depth-first search (DFS) approach.

3. Code Implementation in Different Languages

3.1 Cracking the Safe C++

class Solution {
public:
	string crackSafe(int n, int k) {
		unordered_map<string,int> m;
		string ans="";
		for(int i=0;i<n-1;i++)
		{
			ans+='0';
		}

		for(int i=0;i<pow(k,n);i++)
		{
			string temp=ans.substr(ans.size()-n+1,n-1);
			m[temp]=(m[temp]+1)%k;
			ans+=('0'+m[temp]);
		}

		return ans;
	}
};

3.2 Cracking the Safe Java

class Solution {
    public String crackSafe(int n, int k) {
        Set<String> visited = new HashSet<String>();
        String res = "";
        for(int j = 0; j < n; j++){
            res+=0;
        }
        int total = 1;
        for(int i = 0; i < n; i++){
            total *= k;
        }
        total += n-1;
        res=DFS(res, n, k, visited, total);
        return res;
    }
    private String DFS(String res, int n, int k, Set<String> visited, int total){
        int len = res.length();
        visited.add(res.substring(len-n, len));
        for(int i = 0; i < k; i++){
            if(!visited.contains(res.substring(len-n+1, len)+i)){
                String tmp = DFS(res+i, n, k, visited, total);
                if(tmp.length() == total){
                    res = tmp;
                    break;
                }
                visited.remove(res.substring(len-n+1, len)+i);
            }
        }     
        return res;
    }
}

3.3 Cracking the Safe JavaScript

var crackSafe = function (n, k) {
    if (n === 1 &amp;&amp; k === 1) return '0'
    const visited = new Set()
    const seq = []
    const prefix = '0'.repeat(n - 1)
    dfs(prefix, seq, visited, k)
    seq.push(prefix)
    return seq.join('')
}

const dfs = (prefix, seq, visited, k) =&gt; {
  for (let i = 0; i &lt; k; i++) {
    const combination = prefix + i.toString()
    if (visited.has(combination)) continue
    visited.add(combination)
    dfs(combination.slice(1), seq, visited, k)
    seq.push(i)
  }
}

3.4 Cracking the Safe Python

class Solution(object):
    def crackSafe(self, n, k):
        if n == 1:
            return ''.join(map(str, range(k)))
        seen = set()
        result = []
        start_node = "0" * (n - 1)
        self.dfs(start_node, k, seen, result)
        return "".join(result) + start_node

    def dfs(self, node, k, seen, result):
        for i in range(k):
            edge = node + str(i)
            if edge not in seen:
                seen.add(edge)
                self.dfs(edge[1:], k, seen, result)
                result.append(str(i))

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(kⁿ)	O(kⁿ)
Java	O(kⁿ)	O(kⁿ)
JavaScript	O(kⁿ)	O(kⁿ)
Python	O(kⁿ)	O(`kⁿ`)

The DFS explores all kⁿ combinations, and the map m stores kⁿ entries.
The code implements a De Bruijn sequence construction using a DFS-based Eulerian path traversal.
It efficiently generates a sequence that contains all possible combinations of n digits from 0 to k-1 exactly once.
The time and space complexity for all implementations is O(kⁿ).