We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary String With Substrings Representing 1 To N

Difficulty: Medium

Problem 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.

Key Insights

  • We need to check if the binary representations of all integers from 1 to n are contained within the string s.
  • The binary representation of an integer can be obtained using the built-in bin function in Python or similar methods in other languages.
  • The length of the binary representation can vary, with the maximum being the binary representation of n.
  • We need to ensure that all required binary strings (from 1 to n) are actually substrings of s.

Space and Time Complexity

Time Complexity: O(n * k), where n is the range of numbers to check (1 to n) and k is the average length of their binary representations. Space Complexity: O(1) for auxiliary space, not counting the space used to store the binary representations themselves.

Solution

To solve this problem, we can iterate through each integer from 1 to n, convert it to its binary representation, and check if that representation is a substring of the given string s. We will use string methods to perform the substring check.

Code Solutions

def queryString(s: str, n: int) -> bool:
    # Iterate through all numbers from 1 to n
    for i in range(1, n + 1):
        # Get binary representation of the current number
        binary_representation = bin(i)[2:]  # Skip the '0b' prefix
        # Check if it is a substring of s
        if binary_representation not in s:
            return False
    return True
← Back to All Questions