LeetCode 1016 - Binary String With Substrings Representing 1 To N

The problem asks us to determine whether a given binary string s contains all binary representations of integers from 1 to n as substrings.

leetcodemediumhash-tablestringbit-manipulationsliding-window

LeetCode Problem 1016

Difficulty: 🟡 Medium
Topics: Hash Table, String, Bit Manipulation, Sliding Window

Solution

Problem Understanding

The problem asks us to determine whether a given binary string s contains all binary representations of integers from 1 to n as substrings. In other words, for every integer i such that 1 <= i <= n, if you convert i to its binary form, that binary string must appear somewhere consecutively in s.

The input s is a binary string of length up to 1000, containing only '0' and '1'. The input n can be as large as 1 billion (10^9), which is significant because it means we cannot afford to generate all numbers and search for their binary forms naïvely; this would be computationally infeasible for large n.

Important edge cases include small n values (like 1), binary strings starting with zeros, and n values that exceed the maximum length of substrings in s (since the binary representation of very large numbers could be longer than s). The problem guarantees that s contains only valid binary characters, so we do not need to validate input.

Approaches

Brute Force Approach

The brute-force approach would involve iterating over every integer from 1 to n, converting it to a binary string, and checking if it exists as a substring of s. This approach is straightforward and correct, but it is too slow for large n because the number of checks grows linearly with n, and each substring search is O(L) in the worst case where L is the length of s. Since n can be up to 10^9, this approach is not feasible.

Optimal Approach

The key insight is that we do not need to check every number up to n if the binary representation length exceeds the length of s. The binary length of n is len(bin(n)) - 2, which is the maximum number of bits we need to consider. Therefore, instead of checking all numbers individually, we can use a sliding window over s to extract all possible binary substrings of length up to len(bin(n)) - 2, convert them to integers, and mark them as seen. If all integers from 1 to n are observed in this process, we return true.

This approach reduces the complexity drastically because we process the string s once and consider substrings efficiently, rather than generating all numbers up to n.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * len(s)) O(1) Checks each number up to n in s, too slow for large n
Optimal O(len(s) * log n) O(n) Uses sliding window to capture all possible binary substrings, feasible even for large n

Algorithm Walkthrough

  1. Compute the binary length of n using len(bin(n)) - 2. This gives the maximum substring length we need to consider in s.
  2. Initialize a set to store integers seen in the binary substrings of s.
  3. Iterate over each starting index i of s and, for each index, iterate over possible substring lengths 1 to the binary length of n. Convert each substring to an integer using base 2.
  4. If the integer is between 1 and n, add it to the set of seen numbers.
  5. After processing all substrings, check if the size of the set equals n. If yes, return true, otherwise return false.

Why it works: The algorithm guarantees that all substrings of interest (lengths corresponding to possible numbers from 1 to n) are considered. By collecting them in a set, we ensure duplicates do not affect the count, and the final check confirms whether all required integers are present.

Python Solution

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        max_len = len(bin(n)) - 2
        seen = set()
        
        for i in range(len(s)):
            num = 0
            for j in range(i, min(i + max_len, len(s))):
                num = (num << 1) | int(s[j])
                if 1 <= num <= n:
                    seen.add(num)
            if len(seen) == n:
                return True
        return len(seen) == n

The Python implementation uses a nested loop where the outer loop iterates over the start index of substrings, and the inner loop constructs integers efficiently using bitwise left shift and OR. We stop early if all numbers are found, optimizing runtime. The set seen keeps track of all unique integers seen so far.

Go Solution

func queryString(s string, n int) bool {
    maxLen := len(fmt.Sprintf("%b", n))
    seen := make(map[int]struct{})
    
    for i := 0; i < len(s); i++ {
        num := 0
        for j := i; j < len(s) && j < i+maxLen; j++ {
            num = (num << 1) | int(s[j]-'0')
            if num >= 1 && num <= n {
                seen[num] = struct{}{}
            }
        }
        if len(seen) == n {
            return true
        }
    }
    return len(seen) == n
}

In Go, we use a map instead of a set, with empty structs as values to minimize memory. Bitwise operations build the number as in Python, and early termination is applied.

Worked Examples

Example 1

Input: s = "0110", n = 3

i j substring num seen
0 0 "0" 0 {}
0 1 "01" 1 {1}
0 2 "011" 3 {1,3}
1 1 "1" 1 {1,3}
1 2 "11" 3 {1,3}
1 3 "110" 6 {1,3}
2 2 "1" 1 {1,3}
2 3 "10" 2 {1,2,3}

All numbers 1 to 3 are seen, output is true.

Example 2

Input: s = "0110", n = 4

Following similar steps, number 4 is never seen. Output is false.

Complexity Analysis

Measure Complexity Explanation
Time O(len(s) * log n) Outer loop iterates over string, inner loop iterates up to binary length of n.
Space O(n) The set stores all integers from 1 to n.

The time complexity is efficient because log n is the maximum number of bits for n, which is far smaller than n itself. Space complexity is linear in n because we only store numbers that appear.

Test Cases

# test cases
assert Solution().queryString("0110", 3) == True  # all numbers 1 to 3 present
assert Solution().queryString("0110", 4) == False # number 4 missing
assert Solution().queryString("1", 1) == True     # edge case: smallest input
assert Solution().queryString("0", 1) == False    # edge case: number 1 not present
assert Solution().queryString("1111111111", 5) == True  # repeated digits, all numbers present
assert Solution().queryString("1010", 2) == True  # only numbers 1 and 2
assert Solution().queryString("1010", 3) == False # number 3 missing
Test Why
"0110", 3 Validates all numbers exist
"0110", 4 Checks failure when a number is missing
"1", 1 Edge case with minimal string and n
"0", 1 Edge case where n cannot be formed
"1111111111", 5 Tests repeated digits, should still cover all numbers
"1010", 2 Checks smaller n subset of string
"1010", 3 Ensures algorithm correctly identifies missing numbers

Edge Cases

One important edge case is when s is very short and n is larger than the possible numbers that can be represented with the length of s. For example, s = "1" and n = 2. Our solution handles this by only adding numbers within 1 to n and checking the final set size.

Another edge case is when s contains many repeated digits, such as "111111". The algorithm still correctly identifies all possible numbers by sliding the window over every starting index, ensuring no number is missed.

A third edge case occurs when n is very large, like 10^9. Direct enumeration would fail, but our algorithm only