1016.md

1016. Binary String With Substrings Representing 1 To N

Solution 1 (time O(len(s)*log(n)), space O(n))

class Solution(object):
    def queryString(self, s, n):
        """
        :type s: str
        :type n: int
        :rtype: bool
        """
        seen = set()
        s = list(map(int, s))
        for i, x in enumerate(s):
            if x == 0:
                continue
            j = i + 1
            while x <= n:
                seen.add(x)
                if j == len(s):
                    break
                x = (x << 1) | s[j]
                j += 1
        return len(seen) == n