# Cracking the Safe LeetCode Solution

Here, We see Cracking the Safe LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## 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 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.

## Cracking the Safe LeetCode Solution 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;
}
};Code language: PHP (php)

## Cracking the Safe LeetCode Solution 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();
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;
}
}Code language: JavaScript (javascript)

## Cracking the Safe LeetCode Solution JavaScript

var crackSafe = function (n, k) {
if (n === 1 && 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) => {
for (let i = 0; i < k; i++) {
const combination = prefix + i.toString()
if (visited.has(combination)) continue
dfs(combination.slice(1), seq, visited, k)
seq.push(i)
}
}Code language: JavaScript (javascript)

## Cracking the Safe LeetCode Solution 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: