Problem Explanation

This problem is based on the concept of binary numbers and strings, and also touches upon substring manipulation in strings.

We are given a binary string S and a positive integer N. The binary string S consists only of '0's and '1's.

Our task is to check whether the binary representation of every integer from 1 to N is a substring of the given binary string S.

A substring is a contiguous sequence of characters within a string. For example, in the string "abcdef", some of the substrings are "abc", "de", "f", "bcd" etc.

We need to return true if for every integer X from 1 to N, the binary representation of X is a substring of S. Otherwise, we return false.

Example

Input: S = "0110" N = 3

Explanation: In this example, we see that the binary representations of the numbers from 1 to 3 are '1', '10', and '11' respectively. If we look at the string S, we can see all of these binary numbers are present as substrings in S.

Output: true

Solution Approach

This approach is based on the concept of binary bitset and string manipulation.

In the provided solution, we are running a loop from n to n/2, for each iteration we are converting the integer i to its binary representation using bitset and storing it in binary. The binary number is then reduced to remove leading zeros. After generating the binary representation, the solution checks if this binary is a substring in S. If at any point, the solution finds a number for which the binary representation isn't in S, it immediately returns false. If it doesn't find such a number after looping from n to n/2, it ends the loop and returns true.

Solution Python

1
2python
3class Solution:
4    def queryString(self, s: str, n: int) -> bool:
5        for i in range(n, n//2, -1): 
6            binary = bin(i)[2:] #Converting integer to binary
7            if binary not in s:
8                return False
9        return True

Solution JavaScript

In JavaScript, we will use a similar approach. In place of the bin function that python provides, we can use JavaScript's toString(2) function to convert integers to binary representation.

Here is the code for JavaScript:

1
2javascript
3var queryString = function(s, n) {
4    for(let i = n; i > n/2; i--){
5        let binary = (i).toString(2);
6        if(!s.includes(binary)){
7            return false;
8        }
9    }
10    return true;
11};

Solution Java

In Java, we can use the built-in function Integer.toBinaryString(i) to convert integers to their binary representation. We will also use a StringBuilder to build and manipulate strings since they are mutable in Java unlike normal Strings.

1
2java
3class Solution {
4    public boolean queryString(String S, int N) {
5        for (int i = N; i > N / 2; i--) {
6            String binary = Integer.toBinaryString(i);
7            if (!S.contains(binary)) {
8                return false;
9            }
10        }
11        return true;
12    }
13}

Here, we go from N to N/2 and for each i, we convert it to its binary representation and check if it's a substring in S.

In these solutions, time complexity is O(N) because in the worst-case scenario we go through each number from N to N/2.