1090. Shortest Lock Sequence
A storage locker uses a keypad with the digits 0 to k-1. Its secret code is a string of exactly n digits (leading zeros are allowed), and the locker opens as soon as the last n keys pressed spell the code. There is no reset key and no limit on attempts.
You do not know the code, so you want to press one fixed sequence of keys that is guaranteed to open the locker whichever code was set. Return a shortest digit string in which every possible n-digit code appears as a contiguous substring.
Any shortest string is accepted; the answer is checked for length and coverage, not for a particular spelling.
Example 1
- Input:
- n = 1, k = 3
- Output:
- "012"
- Explanation:
Single-digit codes 0, 1 and 2 each need their own key press, so a shortest string has length 3, for example
"012".
Example 2
- Input:
- n = 2, k = 2
- Output:
- "00110"
- Explanation:
The four codes 00, 01, 10, 11 all appear in
"00110", which has the minimum length 5.
Example 3
- Input:
- n = 2, k = 3
- Output:
- "0010211220"
- Explanation:
There are nine two-digit codes, so a shortest string has length 10, and some arrangement of digits 0..2 achieves it.
Constraints
1 ≤ n
1 ≤ k ≤ 10
k^n ≤ 105
How this problem is judged
- Answers
- Any valid answer is accepted. A checker tests yours against the problem's rules.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(k^n)
- Space
- O(k^n)