Problem statement

https://leetcode.com/problems/cracking-the-safe/

Solution 1

Our guess, that the length of final string will be k^n + n - 1 and it will have k^n different substrings of length n. Actually, this is true and this string can be constructed and we can use dfs with backtracking to construct this string. Let us keep set of already checked passwords. In dfs, we use build string so far: so we add one more symbol in the end and check if last n elements in our set or not.

Complexity

It is difficult to estimate time complexity of this approach, but in practice it works only 2 times slower than the next one.

Code

class Solution:
    def crackSafe(self, n, k):
        self.cands_set = set(["0"*n])
        self.sol = ""

        def dfs(build):
            if self.sol != "": return
            if len(self.cands_set) == k**n:
                self.sol = build
                return
            for j in range(k):
                new = (build[-n+1:] if n > 1 else '') + str(j)
                if new not in self.cands_set:
                    self.cands_set.add(new)
                    dfs(build + str(j))
                    self.cands_set.remove(new)

        dfs("0"*n)
        return self.sol

Solution 2

Alternative way is to note, that we can look at this problem as graph, where we have k^{n-1} nodes and k connection from each node. For example for n = 3 and k = 2 we have the following graph: 00: [00, 01], 10: [00, 01], 01: [10, 11], 11: [10, 11]. Then we need to find path, using all edges, that is Euler path.

Complexity

There will be k^n edges, but we need O(n) time to process one node. So finally, we have O(k^n * n) time and space complexity.

Code

class Solution:
    def crackSafe(self, n, k):
        if n == 1: return "0123456789"[:k]
        
        cands = ["".join(u) for u in product(map(str, range(k)), repeat = n-1)]
        targets = defaultdict(list)
        for a in cands:
            for b in range(k):
                targets[str(b)+a[:n-2]] += [a]

        route = []
        def dfs(node):
            while targets[node]:
                dfs(targets[node].pop())
            route.append(node)
    
        dfs("0"*(n-1))
        return route[0] + "".join(t[0] for t in route[1:])

Remark

Finally, there is O(k^n) solution, where we directly construct our string, but in my opinion it is too mathematical and no way you invent this in 1 hour.