Crack the Safe
Preview mode. Log in to edit, run, submit, and save progress.
Hard
Crack the Safe
A safe unlocks when the last n typed digits match its password. Each digit is from 0 to k - 1. Return any shortest string that guarantees every possible password of length n appears as a substring. Note: Multiple shortest valid strings may exist. For judging, return the string generated by the standard DFS construction that starts with n - 1 zeroes, tries digits from 0 to k - 1, and appends each digit after the recursive call.
Examples
Example 1
Input:
n = 1, k = 2
Output:
10
Approach hint
There are k^n possible passwords.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.
solution.cpp