Practice/Google/Leetcode 753. Cracking the Safe

Leetcode 753. Cracking the Safe

CodingMust

Problem

You need to construct the shortest possible string that contains every possible password of length n using digits from 0 to k-1 as a contiguous substring. Each unique password must appear at least once within the final string.

For example, if n = 2 and k = 2, there are four possible passwords: "00", "01", "10", and "11". You need to find the shortest string where all four appear as substrings.

This problem relates to constructing what's known in graph theory as a special cyclic sequence where overlapping helps minimize total length.

Requirements

1. Return a string containing only digits from 0 to k-1
2. Every possible password of length n must appear as a contiguous substring
3. The returned string should be of minimal length
4. If multiple valid strings exist of the same minimal length, any one is acceptable

Constraints

• 1 ≤ n ≤ 4
• 1 ≤ k ≤ 10
• k^n ≤ 4096 (total number of possible passwords)
• The minimal string length will be k^n + n - 1

Examples

Example 1:

Input: n = 1, k = 2 Output: "01" Explanation: All passwords of length 1 are "0" and "1". The string "01" contains both.

Example 2:

` Input: n = 2, k = 2 Output: "00110" Explanation: All passwords of length 2 are "00", "01", "10", "11". The string "00110" contains:

• "00" at index 0
• "01" at index 1
• "11" at index 2
• "10" at index 3 `

Example 3:

Input: n = 2, k = 3 Output: "0010211220" Explanation: This contains all 9 possible length-2 passwords using digits 0, 1, 2.