Scale Engineer

Cracking the Safe

Hard
#0707Time: `O(n * k^n)`. The search space is a graph with `k^n` edges. The DFS will traverse each edge once. At each step, creating the new password string and performing set operations takes `O(n)` time.Space: `O(n * k^n)`. This is dominated by the `visited` set which stores `k^n` passwords of length `n`. The recursion stack can also go as deep as `k^n`.
Algorithms
Depth-First SearchEulerian Circuit
Data structures
Graph

Prompt

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.

 

Constraints:

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= kn <= 4096

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves building the result string incrementally using a backtracking algorithm. We start with an initial password (e.g., n zeros). Then, we try to extend this string one character at a time. At each step, we consider appending each possible digit. If appending a digit creates a new, unseen password, we make that move and continue the search recursively. If we hit a dead end or a path that doesn't lead to a full solution, we backtrack by undoing the last move. This process continues until we have generated a string that contains all k^n possible passwords.

Algorithm

  • Use a HashSet<String> to keep track of all the unique n-digit passwords we have formed so far.
  • Use a StringBuilder to construct our candidate superstring.
  • Start by initializing the StringBuilder with n zeros and adding this initial password to our set of visited passwords.
  • The core of the algorithm is a recursive dfs function that returns true upon finding a complete solution.
  • In dfs, first check if the size of our visited set equals k^n. If it does, we have found all passwords, and the search is complete, so we return true.
  • If not, take the last n-1 characters from our StringBuilder. This forms the prefix for the next potential password.
  • Loop through all possible digits d. Append d to the prefix to form a newPassword.
  • If newPassword is not in our visited set, it's a valid next move. Add newPassword to the set, append d to our StringBuilder, and make a recursive call to dfs.
  • If the recursive call returns true, it means a solution was found down that path, so we propagate true up the call stack.
  • If the recursive call returns false, we must backtrack. We remove newPassword from the visited set and delete the last character d from our StringBuilder to explore other possibilities.
  • Since a solution is always possible, this search is guaranteed to find a valid string.

Walkthrough

We use a HashSet<String> to keep track of all the unique n-digit passwords we have formed so far and a StringBuilder to construct our candidate superstring. We start by initializing the StringBuilder with n zeros and adding this initial password to our set of visited passwords. The core of the algorithm is a recursive dfs function that returns true upon finding a complete solution. In dfs, we first check if the size of our visited set equals k^n. If it does, we have found all passwords, and the search is complete, so we return true. If not, we take the last n-1 characters from our StringBuilder to form the prefix for the next potential password. We then loop through all possible digits d, appending d to the prefix to form a newPassword. If newPassword is not in our visited set, it's a valid next move. We add newPassword to the set, append d to our StringBuilder, and make a recursive call to dfs. If the recursive call returns true, it means a solution was found down that path, so we propagate true up the call stack. If the recursive call returns false, we must backtrack by removing newPassword from the visited set and deleting the last character d from our StringBuilder to explore other possibilities. Since a solution is always possible, this search is guaranteed to find a valid string.

class Solution {    private int totalPasswords;    private int n;    private int k;    private Set<String> visited;    private StringBuilder result;     public String crackSafe(int n, int k) {        this.n = n;        this.k = k;        this.totalPasswords = (int) Math.pow(k, n);        this.visited = new HashSet<>();        this.result = new StringBuilder();         for (int i = 0; i < n; i++) {            result.append('0');        }        visited.add(result.toString());         if (dfs()) {            return result.toString();        }        return ""; // Should not be reached    }     private boolean dfs() {        if (visited.size() == totalPasswords) {            return true;        }         String prefix = result.substring(result.length() - n + 1);        for (int i = 0; i < k; i++) {            String password = prefix + i;            if (!visited.contains(password)) {                visited.add(password);                result.append(i);                if (dfs()) {                    return true;                }                // Backtrack                visited.remove(password);                result.deleteCharAt(result.length() - 1);            }        }        return false;    }}

Complexity

Time

`O(n * k^n)`. The search space is a graph with `k^n` edges. The DFS will traverse each edge once. At each step, creating the new password string and performing set operations takes `O(n)` time.

Space

`O(n * k^n)`. This is dominated by the `visited` set which stores `k^n` passwords of length `n`. The recursion stack can also go as deep as `k^n`.

Trade-offs

Pros

  • It's a direct and intuitive application of backtracking for this type of construction problem.

Cons

  • The repeated modification of the result StringBuilder (append and delete) can be slightly less efficient than a single final construction.

  • The deep recursion can potentially lead to a StackOverflowError for the maximum possible k^n (4096), although it's often fine in practice.

Solutions

class Solution {private  Set<Integer> vis = new HashSet<>();private  StringBuilder ans = new StringBuilder();private  int mod;public  String crackSafe(int n, int k) {    mod = (int)Math.pow(10, n - 1);    dfs(0, k);    ans.append("0".repeat(n - 1));    return ans.toString();  }private  void dfs(int u, int k) {    for (int x = 0; x < k; ++x) {      int e = u * 10 + x;      if (vis.add(e)) {        int v = e % mod;        dfs(v, k);        ans.append(x);      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem