Binary String With Substrings Representing 1 To N

MEDIUM

Description

Given a binary string s and a positive integer n, return true if the binary representation of all the integers in the range [1, n] are substrings of s, or false otherwise.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "0110", n = 3
Output: true

Example 2:

Input: s = "0110", n = 4
Output: false

Constraints:

1 <= s.length <= 1000
s[i] is either '0' or '1'.
1 <= n <= 10⁹

Approaches

Checkout 3 different approaches to solve Binary String With Substrings Representing 1 To N. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

The most straightforward way to solve this problem is to follow the problem statement directly. We can iterate through every number from 1 to n, convert each number to its binary form, and then check if that binary string exists within s. If we find even one number whose binary representation is not a substring of s, we know the condition is not met and can stop early. If we successfully check all numbers up to n, the condition is satisfied.

Algorithm

Iterate through each integer i from 1 to n.
For each integer i, convert it to its binary string representation. For example, if i is 3, its binary string is "11".
Check if this binary string is a substring of the input string s.
If, for any i, its binary representation is not found in s, we can immediately return false.
If the loop completes without finding any missing binary representations, it means all integers from 1 to n are represented. Return true.

This brute-force method involves a simple loop from 1 to n. In each iteration, we take the current number i, generate its binary equivalent using a built-in function like Integer.toBinaryString(i), and then use a string searching method like s.contains() to see if this binary string is present in s. While simple to understand and implement, its performance is poor due to the potentially huge number of iterations (up to n) combined with the cost of string searching in each iteration.

class Solution {
    public boolean queryString(String s, int n) {
        for (int i = 1; i <= n; i++) {
            String binaryString = Integer.toBinaryString(i);
            if (!s.contains(binaryString)) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(N * L * log N) Where `N` is the input integer `n`, and `L` is the length of the string `s`. The loop runs `N` times. Inside the loop, converting `i` to binary takes `O(log i)` time, and `s.contains()` takes `O(L * log i)` time in the worst case. This makes the total complexity too high for the given constraints.Space Complexity: O(log n) This is the space required to store the binary string representation of the largest number, `n`.

Pros and Cons

Pros:

Very easy to understand and implement.
It is a direct translation of the problem statement into code.

Cons:

This approach is very slow and will lead to a 'Time Limit Exceeded' error on platforms like LeetCode for larger values of n.
The time complexity is directly proportional to n, which can be up to 10^9.

Code Solutions

Checking out 3 solutions in different languages for Binary String With Substrings Representing 1 To N. Click on different languages to view the code.

class Solution {
public
  boolean queryString(String s, int n) {
    if (n > 1023) {
      return false;
    }
    for (int i = n; i > n / 2; i--) {
      if (!s.contains(Integer.toBinaryString(i))) {
        return false;
      }
    }
    return true;
  }
}

Video Solution

Watch the video walkthrough for Binary String With Substrings Representing 1 To N

Patterns:

Sliding WindowBit Manipulation

Data Structures:

Hash TableString