LeetCode 1016: Binary String With Substrings Representing 1 To N

Problem Restatement

We are given a binary string s and a positive integer n.

We need to return true if every integer from 1 to n can be represented as a substring of s when the substring is interpreted as a binary number.

The official constraints state that 1 <= s.length <= 1000 and 1 <= n <= 10^9.

Input and Output

Function shape:

def queryString(s: str, n: int) -> bool:
    ...

Examples

Example 1:

s = "0110"
n = 3

• 1 in binary: "1" → in "0110" ✓
• 2 in binary: "10" → in "0110" ✓
• 3 in binary: "11" → in "0110" ✓

Answer:

True

Example 2:

s = "0110"
n = 4

• 4 in binary: "100" → not in "0110" ✗

Answer:

False

Key Insight

If n is large enough, this becomes impossible even with a long s. Specifically, a binary string of length L has at most L * (L + 1) / 2 distinct substrings. For all integers 1 to n to be represented, each must correspond to a unique substring. So we only need to check integers down to a practical limit.

For a string s of length 1000, all distinct substrings of length >= 20 are fewer than 1000 * 20 = 20000. Since 2^20 > 10^6, for n > 2 * len(s), the answer is False.

So for n > 2 * len(s), return False. Otherwise, check each integer from n down to 1.

Algorithm

1. If n > 2 * len(s), return False.
2. For each integer i from 1 to n:
   • Convert i to binary string (without the 0b prefix).
   • Check if this binary string is a substring of s.
   • If not, return False.
3. Return True.

Correctness

For large n, the number of integers to check exceeds the number of substrings s can contain, so the answer must be False.

For small n, we directly check each integer.

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Let L = len(s).

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

Implementation

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        if n > 2 * len(s):
            return False

        for i in range(1, n + 1):
            if bin(i)[2:] not in s:
                return False

        return True

Code Explanation

Early return for impossible cases:

if n > 2 * len(s):
    return False

Check each integer’s binary representation:

for i in range(1, n + 1):
    if bin(i)[2:] not in s:
        return False

bin(i)[2:] gives the binary representation without the "0b" prefix.

The in operator checks for substring containment in O(L) time.

Testing

def run_tests():
    s = Solution()

    assert s.queryString("0110", 3) == True
    assert s.queryString("0110", 4) == False
    assert s.queryString("1", 1) == True
    assert s.queryString("0", 1) == False
    assert s.queryString("1111110", 5) == False

    print("all tests passed")

run_tests()