1016. Binary String With Substrings Representing 1 To N

MediumString
Leetcode Link

Problem Description

The problem requires us to determine if a given binary string s contains all the binary representations of numbers from 1 to a given positive integer n as substrings. A substring is a sequence of characters that occur in order without any interruptions within a string. For example, if s = "0110" and n = 3, we need to check if the binary representations of 1 ("1"), 2 ("10"), and 3 ("11") are all present as substrings in s.

To solve the problem, we need to generate the binary representation of each number from 1 to n and verify if each representation is a substring of s.

Intuition

The solution involves a few key observations and steps:

  1. Binary Length: The binary representation of a number grows in length when the number doubles. Therefore, as we approach n, more significant numbers would have longer binary strings, and if they are not found in s, we can determine the answer is false without checking smaller numbers.

  2. Efficient Checking: We start checking from n and go down to n//2. The reasoning is that every binary string that would represent a number from 1 to n//2 will also be a substring of a string representing a number from n//2 to n. For example, "10" for 2 is contained within "110" for 6.

  3. Performance Boundaries: Since the binary length grows with the number size, the code includes a quick exit condition when n is greater than 1000, possibly to avoid performance issues with extremely large strings. However, this condition seems arbitrary and depends on constraints not mentioned in the problem description. It may not be necessary if the input string s is always large enough to potentially contain all representations.

  4. All-encompassing Check: To verify if all binary representations are in s, a Python built-in function all() is used, which checks for the truthiness of all elements in an iterable. In this case, a generator expression checks if each binary representation as a string is a substring of s (bin(i)[2:] in s).

The intuition behind this approach is that by checking the larger half of the range first using string containment operations, one can determine if the binary representations of numbers in the range [1, n] are substrings of the given string s with higher efficiency than checking every single number starting from 1.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The solution approach utilizes a simple and direct method for checking the presence of binary substrings within the given string s. Below are the components and steps of the implementation using the provided Python code:

  1. Function Signature:

    • def queryString(self, s: str, n: int) -> bool: This is the function signature where s is the input string and n is the integer until which we need to check the binary representations. The function returns a Boolean value.

  2. Early Return Condition:

    • if n > 1000: return False: The code immediately returns False if n is more than 1000, implying a performance optimization for large numbers, but as mentioned earlier, this condition may be arbitrary.

  3. Main Checking Loop:

    • return all(bin(i)[2:] in s for i in range(n, n // 2, -1)): Here the algorithm employs Python's built-in function all() which tests if all elements in an iterable are true. The iterable, in this case, is a generator expression that goes through the range of integers from n to n // 2 (integer division by 2) in descending order.

  4. Binary Conversion and Substring Check:

    • bin(i)[2:] in s: For each i in the specified range, the built-in bin() function generates its binary representation as a string and strips off the '0b' prefix with [2:]. Then we check whether this binary representation is a substring of s.

  5. Data Structures:

    • No additional data structures are used in this solution. The input string s and integer n are directly utilized within the algorithm.

  6. Algorithmic Patterns:

    • The algorithm does not use complex patterns or advanced data structures. It relies on Python’s expressive syntax and built-in functions to perform substring checking efficiently.

The loop iterates through only half of the specified range (from n to n // 2) in reverse order because if i can be represented within s as a binary string, all smaller numbers can also be substrings of those representations or will have occurred earlier within the binary sequence. This approach takes advantage of the fact that binary representations of numbers are nested within those of larger numbers, providing a significant performance improvement over checking every single number individually from 1 to n.

In summary, the code leverages Python's capabilities to check for the presence of each binary representation of numbers in the given range within the string s succinctly and efficiently.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

To illustrate the solution, let's consider an example where s = "01101101" and n = 4. We would like to determine if the binary representations of numbers from 1 to 4, which are "1" (1), "10" (2), "11" (3), and "100" (4), appear as substrings in s.

Steps:

  1. Check for Early Return: The first check in our solution is to see if n is greater than 1000. In this case, n = 4, so we do not return early and proceed.

  2. Initialize the Main Loop: Starting with i = 4 and iterating down to i = 2 (half of n), we check each binary representation to see if it's a substring in s.

  3. Binary Conversion:

    • For i = 4, we convert 4 to binary, getting "100". Check if "100" is in s. It is not, so we could already return False. However, continue for illustration purposes.
    • For i = 3, convert 3 to binary, yielding "11". Check if "11" is a substring of s, which it is, as s is "01101101".
    • For i = 2, convert 2 to binary to get "10". We then check if "10" is part of s, and indeed, it is present.

  4. Evaluate with all() Function: Use the all() function to verify whether all these checks (i = 4 to i = 2) are True. Since "100" was not found, all() will return False.

  5. No Additional Data Structures: We have not used additional data structures outside the string s and the numbers we're checking.

  6. Conclusion: Since not all binary representations from 1 to 4 were found as substrings in s ("100" was missing), the all() function will evaluate to False. Therefore, the given string s does not contain all binary representations as substrings.

This step-by-step walkthrough demonstrates the simplicity and efficiency of the approach by focusing on checking only the necessary binary representations and utilizing Python's built-in tools.

Solution Implementation

1class Solution:
2    def query_string(self, string: str, upper_bound: int) -> bool:
3        # If the upper bound (n) is greater than 1000, return false as per the given logic.
4        if upper_bound > 1000:
5            return False
6      
7        # 'all' checks whether all elements in the iterable are True.
8        # The loop starts from 'upper_bound' and goes till 'upper_bound // 2' (integer division by 2), moving backwards.
9        # 'bin(i)[2:]' converts the integer 'i' to its binary representation in string format, stripping off the '0b' prefix.
10        # 'in string' checks if each binary representation is a substring of the input string 'string'.
11        return all(bin(i)[2:] in string for i in range(upper_bound, upper_bound // 2, -1))
12
13# Example usage:
14# sol = Solution()
15# result = sol.query_string("0110", 3)
16# print(result) # This would print 'True' if all binary numbers from n to n//2 are substrings of "0110"
17
1class Solution {
2
3  /**
4   * Checks if all binary representations of numbers from 1 to n are substrings of the string s.
5   * 
6   * @param s The string in which binary representations are to be searched.
7   * @param n The maximum value up to which binary representations should be checked.
8   * @return True if all binary representations from 1 to n are found in s, otherwise False.
9   */
10  public boolean queryString(String s, int n) {
11    // If n is greater than the maximum allowed value (as binary representation within the string),
12    // which is 2^10 - 1 = 1023 for a 10-bit binary number, return false as the condition can't be met.
13    if (n > 1023) {
14      return false;
15    }
16    // Iterate from n down to n / 2 since every number smaller than n/2 is a binary substring of a number
17    // that is larger than n/2 (because the binary representation of a number is also a suffix of the
18    // binary representation of its double).
19    // If a substring representing the binary of i is not found within string s, return false.
20    for (int i = n; i > n / 2; i--) {
21      if (!s.contains(Integer.toBinaryString(i))) {
22        return false;
23      }
24    }
25    // Return true if all required binary substrings have been found.
26    return true;
27  }
28}
29
1#include <bitset>
2#include <string>
3
4class Solution {
5public:
6    // Function to check if all binary representations of numbers 
7    // from 1 to n are substrings of the input string s.
8    bool queryString(std::string s, int n) {
9        // Early exit condition if n is greater than the maximum 
10        // value representable with 10 binary digits.
11        if (n > 1023) {
12            return false;
13        }
14        // Loop through numbers starting from n to half of n 
15        // since the bit representation of numbers less than n/2 
16        // will always be contained in the bit representation of 
17        // numbers between n/2 and n.
18        for (int i = n; i > n / 2; --i) {
19            // Convert the number to binary (bitset) and then to string.
20            std::string binaryString = std::bitset<32>(i).to_string();
21            // Remove leading zeroes from the binary string.
22            binaryString.erase(0, binaryString.find_first_not_of('0'));
23            // Check if the resulting binary string is a substring of s.
24            if (s.find(binaryString) == std::string::npos) {
25                // If not found, return false immediately.
26                return false;
27            }
28        }
29        // All required binary representations are substrings of s. Return true.
30        return true;
31    }
32};
33
1/**
2 * Checks if a binary string represents all numbers from 1 to n.
3 * 
4 * @param {string} binaryString - The string consisting of binary digits.
5 * @param {number} maxNumber - The maximum number to check up to (inclusive).
6 * @returns {boolean} - Returns true if all numbers from 1 to maxNumber are 
7 * represented in the binaryString, otherwise false.
8 */
9function queryString(binaryString: string, maxNumber: number): boolean {
10    // Check if the maxNumber is larger than the largest number that can be represented
11    // with a 10-bit binary number, which is 1023.
12    if (maxNumber > 1023) {
13        return false;
14    }
15    // Iterate from the maxNumber down to half of it, since every number from 1 to n / 2
16    // will be a substring of the binary representation of numbers from n / 2 + 1 to n.
17    for (let currentNum = maxNumber; currentNum > maxNumber / 2; --currentNum) {
18        // Convert the current number to its binary string representation.
19        const binaryRepresentation = currentNum.toString(2);
20        // Check if the current binary representation is a substring of binaryString.
21        // If it is not found, the method returns -1, therefore, return false.
22        if (binaryString.indexOf(binaryRepresentation) === -1) {
23            return false;
24        }
25    }
26    // If all necessary binary representations are found in the string, return true.
27    return true;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

The time complexity of the provided code can be determined by analyzing the two main operations: the all function and the string containment check in.

Time Complexity:

  • The all function iterates over the range from n to n // 2, decreasing by 1 each time. This results in approximately n/2 iterations.
  • For each iteration, the string containment check in is performed, which, in the worst case, has a complexity of O(m), where m is the length of the string s.

Therefore, the overall worst-case time complexity is O(m * n/2), as the containment check is performed n/2 times.

Space Complexity:

  • No extra space is used for data storage that scales with the input size; only a fixed number of variables are used.
  • The binary representation string created for each number i is temporary and its length is at most O(log(n)).

Hence, the space complexity is O(1), which means it is constant since the space required does not grow with the input size n or the string length m.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫