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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary String With Substrings Representing 1 To N

Number: 1065

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary string s and a positive integer n, determine if every integer in the range [1, n] has its binary representation present as a contiguous substring in s. A substring is defined as a contiguous sequence of characters in the string.

Key Insights

  • The binary representation of a number i has a length of floor(log2(i)) + 1. Thus, numbers larger than n will have representations longer than len(bin(n)) - 2.
  • Instead of iterating over [1, n] (which is infeasible when n is large), we can iterate over s and consider all substrings with lengths up to that of n’s binary representation.
  • When scanning s, only substrings starting with '1' need to be considered since binary representations do not have leading zeroes.
  • Use a sliding window limited by the maximum possible length (L = len(bin(n)) - 2) to extract and convert substrings to integer values.
  • If any substring’s integer value exceeds n, further expanding that substring only increases its value, so the inner loop can be terminated early.
  • Finally, if the set of found numbers equals n (i.e. contains every number from 1 to n), then return true; otherwise, return false.

Space and Time Complexity

Time Complexity: O(m * L) where m is the length of s and L is the maximum binary length (approximately 30 for n up to 10^9). This is efficient because L is a small constant compared to m. Space Complexity: O(n) in the worst case for storing all the numbers in the range [1, n], but practically the number of distinct substrings extracted is bounded by m * L.

Solution

The solution leverages a sliding window approach over the binary string s. For every index in s where the character is '1', we try to form a number by extending the window up to a maximum length L (derived from the binary length of n). As we build the number, if it exceeds n, we stop extending that substring since subsequent digits will only increase the number. We add each valid number (<= n) to a hash set. Finally, by comparing the set’s size with n, we ensure all integers from 1 to n are present as substrings. This approach avoids the inefficiency of checking every integer from 1 to n one by one.

Code Solutions

# Python solution for Binary String With Substrings Representing 1 To N

def queryString(s: str, n: int) -> bool:
    # Calculate maximum length required based on the binary representation of n
    max_len = len(bin(n)) - 2  # subtracting 2 for the '0b' prefix
    found_numbers = set()
    
    # Iterate over each character in s where it starts with '1'
    for i in range(len(s)):
        if s[i] == '1':
            num = 0  # current number formed from substring s[i:j+1]
            # Extend substring up to the maximum necessary length
            for j in range(i, min(len(s), i + max_len)):
                num = (num << 1) | (int(s[j]))  # update num by shifting left and adding current digit
                if num > n:
                    # No need to extend further if the number exceeds n
                    break
                found_numbers.add(num)
    
    # Check if all numbers from 1 to n are found
    return len(found_numbers) == n

# Example usage:
# s = "0110", n = 3 should return True, while n = 4 should return False.
print(queryString("0110", 3))  # Output: True
print(queryString("0110", 4))  # Output: False
← Back to All Questions