Cracking the Safe Solution in Java

Navigate to Other Solutions


class Solution {
  public String crackSafe(int n, int k) {
    final String allZeros = "0".repeat(n);
    StringBuilder sb = new StringBuilder(allZeros);
    dfs((int) Math.pow(k, n), n, k, new HashSet<>(Arrays.asList(allZeros)), sb);
    return sb.toString();
  }

  private boolean dfs(int passwordSize, int n, int k, Set seen, StringBuilder path) {
    if (seen.size() == passwordSize)
      return true;

    StringBuilder prefix = new StringBuilder(path.substring(path.length() - n + 1));

    for (char c = '0'; c < '0' + k; ++c) {
      prefix.append(c);
      final String prefixStr = prefix.toString();
      if (!seen.contains(prefixStr)) {
        seen.add(prefixStr);
        path.append(c);
        if (dfs(passwordSize, n, k, seen, path))
          return true;
        path.deleteCharAt(path.length() - 1);
        seen.remove(prefixStr);
      }
      prefix.deleteCharAt(prefix.length() - 1);
    }

    return false;
  }
}

Problem Description

Imagine you’re trying to crack a safe, but instead of a simple 4-digit code, you’re faced with a safe that requires a code of length n using digits from 0 to k-1. You need to generate a sequence that contains every possible combination of these codes as a substring.

In simpler terms, the problem is to find the shortest possible string that contains every possible combination of n digits using k different digits. Think of it as trying to remember every possible combination of your friends' birthdays, but instead, you’re just trying to crack a safe.

Approach

The approach used in this solution is a depth-first search (DFS) algorithm. The algorithm starts with a string of n zeros and attempts to build the shortest string that contains all possible combinations of n digits using k different digits. It explores each possible digit to append to the current string and checks if the resulting substring has been seen before. If it hasn’t, it adds it to the set of seen combinations and continues the search. If all combinations are found, it returns the constructed string.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(kⁿ)
Space Complexity	O(kⁿ)

Real-World Example

Think of this problem like trying to create a master key for a series of lockers, where each locker has a unique combination. You want to ensure that your key can open every locker without having to create a new key for each one. The Cracking the Safe problem is essentially about finding that master key that can unlock every possible combination of lockers.