Problem statement

https://binarysearch.com/problems/Non-Consecutive-String/

Solution

There will be 2^(n-1) strings, start with 0, 1 or 2. We can find the first digit, subtracting this number from k until we can. Then we have 2^(n-2) strings with given next digit and so on. So, we can reconstruct answer digit by digit.

Complexity

It is O(n) for time and space, because we can assume that k < 3*2^(n-1), in the opposite case we return "".

Code

class Solution:
    def solve(self, n, k):
        arr = [1]
        for i in range(n - 1):
            arr += [arr[-1] * 2]

        arr = arr[::-1]
        ans = []

        if k >= 3*arr[0]: return ""

        for i in range(n):
            cands = [0, 1, 2]
            if i > 0: cands.pop(ans[-1])
            while k >= arr[i]:
                cands.pop(0)
                k -= arr[i]
            ans += [cands[0]]

        return "".join(str(i) for i in ans)