493. Cracking the Safe
A safe is locked by a secret code of n digits, each digit drawn from 0 to k - 1. The keypad has one quirk: it only remembers the last n digits pressed. After every key press it checks whether the most recent n presses spell the code, and it springs open the instant they do.
You get to type one long string of digits and you want it to be guaranteed to open the safe — every one of the k^n possible codes must appear somewhere as a substring of what you type.
Given the integers n and k, return the shortest press sequence that opens the safe, subject to two tie-breaking rules that make the answer unique: the sequence must start with n zeros, and among all shortest sequences starting with n zeros you must return the lexicographically largest one.
Example 1:
Input: n = 1, k = 2
Output: "01"
Explanation: The code is a single digit, either 0 or 1. Pressing "01" tries 0 first and then 1, so the safe opens whatever the code is. It starts with one zero and no shorter sequence can cover both codes.
Example 2:
Input: n = 2, k = 2
Output: "00110"
Explanation: The four possible codes are 00, 01, 11, 10. Sliding a window of width 2 across "00110" produces exactly those four: 00, 01, 11, 10 — each code once, in 5 presses (the minimum, since 4 windows need 4 + 2 - 1 = 5 digits).
Constraints:
- 1 ≤ n ≤ 4
- 1 ≤ k ≤ 10
- k^n ≤ 4096
Hints:
There are k^n codes and a string of length L contains L - n + 1 windows, so the best you can hope for is length k^n + n - 1: every window is a distinct code. Think of each code as something to be "consumed" exactly once.
Model a state as the last n - 1 digits typed. Pressing digit d moves you from state s to state s[1:] + d and consumes the code s + d. You need a walk that uses every possible code-edge exactly once — an Eulerian circuit.
Try digits from largest to smallest, marking each new code as seen, and backtrack if you get stuck. The first complete string found this way is exactly the canonical answer — and a classical de Bruijn result says the greedy never actually needs to backtrack.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 1, k = 2
Expected output: "01"