Problem Description

Given a binary string s and a positive integer n, determine if for every integer x in the range 1 to n (inclusive), there exists a substring of s that, when interpreted as a binary number (without leading zeros), is equal to x.

In other words, does s contain all binary representations (as substrings) of every number from 1 to n?

• Each substring must not have leading zeros (except for the number 0 itself, which is not in the range).
• You may use overlapping substrings.
• s may be quite long, and n may be up to 1000.

Thought Process

At first glance, this problem seems to require checking every possible substring of s and seeing if it matches any binary representation of numbers from 1 to n. However, this brute-force approach is inefficient, especially for large strings.

We need to find a way to efficiently check if all required binary numbers are present as substrings. The key realization is that the number of binary representations we need to check is limited by n, not by the length of s. Also, since substrings can overlap, we can use a set to track which numbers we've found.

Instead of generating all substrings, we can iterate through s, extract short substrings (up to the length of the binary representation of n), and check if they match any required number. This reduces unnecessary checks and speeds up the process.

Solution Approach

• Step 1: For numbers 1 to n, store their binary representations as strings (without leading zeros) in a set called targets.
• Step 2: Determine the maximum length of binary representations needed (i.e., len(bin(n)[2:])).
• Step 3: Iterate over the string s. For each starting index, extract substrings of lengths from 1 up to the maximum binary length.
• Step 4: For each substring, check:
  • It does not start with '0' (to avoid leading zeros).
  • If it's in targets, remove it from the set (since we've found it).
• Step 5: At the end, if targets is empty, it means we found all required numbers as substrings; otherwise, return False.

This approach ensures we only check relevant substrings and efficiently track which numbers have been found.

Example Walkthrough

Let's use s = "0110" and n = 3.

• Binary representations needed: "1", "10", "11"
• Maximum binary length: 2
• Iterate through s:
  • At index 0: "0" (skip, starts with '0'), "01" (skip, starts with '0')
  • At index 1: "1" (found "1"), "11" (found "11")
  • At index 2: "1" (already found), "10" (found "10")
  • At index 3: "0" (skip, starts with '0')
• All targets found ("1", "10", "11"), so return True.

Time and Space Complexity

• Brute-force approach:
  • Generate all substrings of s: O(L^2), where L is the length of s.
  • Check each substring against up to n targets: O(n).
  • Total: O(L^2 * n), which is inefficient for large inputs.
• Optimized approach:
  • For each index in s, check up to log2(n) substrings (since that's the max binary length).
  • Total: O(L * log n)
  • Space: O(n) for the target set.

The optimized approach is much more efficient, especially for large strings and moderate values of n.

Summary

The challenge is to efficiently check if all binary representations of numbers from 1 to n are present as substrings in s. By focusing only on relevant substrings and using a set to track our progress, we achieve an efficient and elegant solution. The key insights are limiting substring lengths and avoiding unnecessary checks, making the algorithm suitable for large inputs.

Code Implementation

class Solution:
    def queryString(self, s: str, n: int) -> bool:
        targets = set(bin(i)[2:] for i in range(1, n+1))
        max_len = len(bin(n)[2:])
        for i in range(len(s)):
            for l in range(1, max_len+1):
                if i + l <= len(s):
                    sub = s[i:i+l]
                    if sub[0] == '0':
                        continue
                    if sub in targets:
                        targets.remove(sub)
        return not targets
      

class Solution {
public:
    bool queryString(string s, int n) {
        unordered_set<string> targets;
        for (int i = 1; i <= n; ++i) {
            targets.insert(bitset<32>(i).to_string().substr(32 - (int)log2(i) - 1));
        }
        int max_len = 0;
        int temp = n;
        while (temp) {
            max_len++;
            temp >>= 1;
        }
        int L = s.size();
        for (int i = 0; i < L; ++i) {
            for (int l = 1; l <= max_len && i + l <= L; ++l) {
                if (s[i] == '0') continue;
                string sub = s.substr(i, l);
                if (sub[0] == '0') continue;
                if (targets.count(sub)) {
                    targets.erase(sub);
                }
            }
        }
        return targets.empty();
    }
};
      

class Solution {
    public boolean queryString(String s, int n) {
        Set<String> targets = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            targets.add(Integer.toBinaryString(i));
        }
        int maxLen = Integer.toBinaryString(n).length();
        int L = s.length();
        for (int i = 0; i < L; i++) {
            for (int l = 1; l <= maxLen && i + l <= L; l++) {
                String sub = s.substring(i, i + l);
                if (sub.charAt(0) == '0') continue;
                if (targets.contains(sub)) {
                    targets.remove(sub);
                }
            }
        }
        return targets.isEmpty();
    }
}
      

var queryString = function(s, n) {
    const targets = new Set();
    for (let i = 1; i <= n; i++) {
        targets.add(i.toString(2));
    }
    const maxLen = n.toString(2).length;
    for (let i = 0; i < s.length; i++) {
        for (let l = 1; l <= maxLen && i + l <= s.length; l++) {
            let sub = s.substring(i, i + l);
            if (sub[0] === '0') continue;
            if (targets.has(sub)) {
                targets.delete(sub);
            }
        }
    }
    return targets.size === 0;
};