#753
Cracking the Safe
expert · 1235 · lc hard +32 · verified · 58.4% accepted · 662 likes · top 55%
Description
A safe's password is an n-digit sequence where each digit is in [0, k - 1]. After each keystroke the safe checks the most recent n digits entered; if they match the password, the safe unlocks. For example, entering "012345" covers the 3-digit windows "012", "123", "234", "345", etc.
Return any string of minimum total length that is guaranteed to contain every possible n-digit password as a contiguous substring — so that the safe unlocks no matter what the password is.
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.
Code
1
2
3