LeetCode 1016: Binary String With Substrings Representing 1 To N

Meta Data

#

Difficulty: medium First Attempt: 2026-01-04

• Submissions: Memory Limit Exceeded → Wrong Answer ×4 → Accepted

Approach

#

n can reach 10^9, but s has at most 1000 characters.

Key observation: every number in (n/2, n] has the same binary length L, and there are about n/2 of them. s has at most len(s) substrings of length L, so whenever n/2 > len(s) some number is missing. When the answer is True, n must be small (about <= 2000).

Two approaches:

1. Check downward from n: test each number with bin(i)[2:] in s. For large n the first few checks fail; for small n there are only a few thousand checks.
2. Collect with a sliding window: from each 1 in s, extend right while computing the binary value, stopping past n or 30 bits; put every value <= n into a set and check whether its size is n.

My Attempts

#

Solution

#

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        for i in range(n, 0, -1):                  # large numbers first; a big n fails fast
            if bin(i)[2:] not in s:
                return False
        return True

Sliding-window collection version:

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        seen = set()
        for i in range(len(s)):
            if s[i] == "0":
                continue                           # binary representations have no leading 0
            val = 0
            for j in range(i, min(len(s), i + 30)):
                val = val * 2 + (s[j] == "1")
                if val > n:
                    break
                seen.add(val)
        return len(seen) == n

Complexity

#

• Downward check: when the answer is True, n = O(len(s)), and each in is O(len(s) · log n), about O(len(s)^2 · log n) total; for large n it fails within the first few numbers.
• Collection: time O(30 · len(s)), space O(min(n, 30 · len(s))).

Mistakes to Avoid

#

• Storing all of 1..n: n can be 10^9.
• Judging by the number of distinct substrings: leading zeros and values outside 1..n get mixed in.

Interview Explanation

#

s has at most 1000 characters, and all numbers between n/2 and n share one binary length, so for n above roughly twice len(s) the answer must be False. I can check from n downward whether each number is a substring, which fails quickly for large n; or extend up to 30 bits from each 1, collect every value <= n in a set, and compare its size with n, in O(30 · len(s)).