753. Cracking the Safe Hard

1/**
2 * [753] Cracking the Safe
3 *
4 * There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1].
5 * The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit.
6 * 
7 * 	For example, the correct password is "345" and you enter in "012345":
8 * 	
9 * 		After typing 0, the most recent 3 digits is "0", which is incorrect.
10 * 		After typing 1, the most recent 3 digits is "01", which is incorrect.
11 * 		After typing 2, the most recent 3 digits is "012", which is incorrect.
12 * 		After typing 3, the most recent 3 digits is "123", which is incorrect.
13 * 		After typing 4, the most recent 3 digits is "234", which is incorrect.
14 * 		After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks.
15 * 	
16 * 	
17 * 
18 * Return any string of minimum length that will unlock the safe at some point of entering it.
19 *  
20 * Example 1:
21 * 
22 * Input: n = 1, k = 2
23 * Output: "10"
24 * Explanation: The password is a single digit, so enter each digit. "01" would also unlock the safe.
25 * 
26 * Example 2:
27 * 
28 * Input: n = 2, k = 2
29 * Output: "01100"
30 * Explanation: For each possible password:
31 * - "00" is typed in starting from the 4^th digit.
32 * - "01" is typed in starting from the 1^st digit.
33 * - "10" is typed in starting from the 3^rd digit.
34 * - "11" is typed in starting from the 2^nd digit.
35 * Thus "01100" will unlock the safe. "01100", "10011", and "11001" would also unlock the safe.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= n <= 4
41 * 	1 <= k <= 10
42 * 	1 <= k^n <= 4096
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/cracking-the-safe/
48// discuss: https://leetcode.com/problems/cracking-the-safe/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn crack_safe(n: i32, k: i32) -> String {
54        String::new()
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_753() {
66    }
67}
68