You are given a binary string s and a positive integer n. Your task is to determine whether the binary representations of all integers from 1 to n (inclusive) appear as substrings within the string s.

A substring is defined as any contiguous sequence of characters that appears within the string. For example, if s = "0110", then "0", "1", "11", "110", "01", "011", and "0110" are all valid substrings.

The function should return true if every integer from 1 to n, when converted to its binary representation (without leading zeros), can be found as a substring in s. Otherwise, return false.

For example:

• If s = "0110" and n = 3:

  • Binary of 1 is "1" - found in s at positions 1 and 2
  • Binary of 2 is "10" - found in s starting at position 2
  • Binary of 3 is "11" - found in s starting at position 1
  • Result: true

• If s = "0110" and n = 4:

  • Binary of 4 is "100" - not found in s
  • Result: false

The first key insight is recognizing that as numbers grow larger, their binary representations become longer. For a string s of length L to contain all binary representations from 1 to n, it must have enough "space" to accommodate all these different binary patterns.

Consider the binary representation lengths:

• Numbers from 1 to 1: require 1 bit ("1")
• Numbers from 2 to 3: require 2 bits ("10", "11")
• Numbers from 4 to 7: require 3 bits ("100" to "111")
• Numbers from 2^k to 2^(k+1) - 1: require k+1 bits

If n is large compared to s, the string cannot hold all the required patterns. Every number in the range (n/2, n] has a binary length of either L or L - 1, where L is the bit length of n. A single starting position in s can begin at most one of them: if the length-L window starting there is a number at most n, its length-(L - 1) prefix equals that number divided by 2, which is at most n/2 and therefore outside the range. So the n - n/2 numbers in that range need at least n - n/2 different starting positions, which forces n - n/2 <= len(s). When n > 2 * len(s) this fails, which explains the if n > 2 * len(s): return False check. It also keeps the loop short, since n is at most 2 * len(s) once the check passes.

The second clever insight involves the checking order. Why check from n down to n//2 + 1 instead of checking all numbers from 1 to n?

If we're missing any number in the range [n//2 + 1, n], we can immediately return false.

Why can we skip checking numbers from 1 to n//2? For any k in [1, n//2], the number 2k is at most n, and the binary form of 2k is the binary form of k followed by a 0. So k appears in s whenever 2k does. Doubling repeatedly, k, 2k, 4k, ... eventually lands in (n/2, n], and every number in that chain has the binary form of k as a prefix. If all numbers in (n/2, n] are present, every smaller number is present too. For instance, if "110" (6 in binary) is in the string, then "11" (3) and "1" (1) are present as prefixes.

This cuts the number of checks in half without losing correctness.

Pattern Learn more about Sliding Window patterns.

The implementation uses a straightforward but optimized approach to solve this problem:

Step 1: Handle Large Values

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

This check immediately returns false for large values of n. Each starting position in s can begin at most one of the numbers in (n/2, n], so those n - n/2 numbers need at least n - n/2 starting positions. When n > 2 * len(s), there are not enough positions.

Step 2: Check Critical Range

Copy
for i in range(n, n // 2, -1):
    if bin(i)[2:] not in s:
        return False
return True

This line does several things:

1. Range Selection: range(n, n // 2, -1) generates numbers from n down to n//2 + 1 in descending order. This checks approximately half of the numbers, specifically the larger half.

2. Binary Conversion: bin(i)[2:] converts each number i to its binary representation and removes the '0b' prefix that Python adds. For example:

   • bin(5) returns '0b101'
   • bin(5)[2:] returns '101'

3. Substring Check: The in operator checks if the binary representation exists as a substring in s. This is a built-in Python operation that efficiently searches for the substring.

4. Early Exit: If any binary representation is not found in s, the loop immediately returns False. If the loop finishes, every checked number was found.

Why This Works:

For any k in [1, n//2], the binary form of 2k is the binary form of k with a 0 appended, and 2k <= n. Repeatedly doubling k gives a number in [n//2 + 1, n] whose binary form starts with the binary form of k. So if every number in the upper half is a substring of s, every number in the lower half is a substring as well, because it is a prefix of one of them.

Time Complexity: O(|s|^2 * log |s|) in the worst case. After the first check, n <= 2 * |s|, so we check at most |s| numbers, and each substring search for a pattern of length O(log n) takes O(|s| * log n) time.

Space Complexity: O(1) if we don't count the space used for binary string conversion, which is temporary and small (O(log n) bits).