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 <= 1000s[i] is either '0' or '1'.1 <= n <= 109Problem Overview: You get a binary string s and an integer n. The task is to verify that every integer from 1 to n, when written in binary, appears as a substring inside s. If even one binary representation is missing, the result is false.
Approach 1: Iterative Binary Check (Time: O(n * |s|), Space: O(log n))
This approach directly follows the problem definition. Iterate through every number from 1 to n, convert the number to its binary representation, and check whether that binary string exists inside s. Most languages provide a substring search operation like find() or contains(), which makes the implementation simple. The key work is repeated substring searches across the string. While straightforward, this approach may become slow when n is large because each number requires generating a binary string and scanning s. The solution relies heavily on efficient string operations.
Approach 2: Extend Range Check (Time: O((n/2) * |s|), Space: O(log n))
This optimization relies on a useful observation about binary representations. If the binary representation of a number x appears in s, then many smaller numbers already appear as substrings inside larger ones. Specifically, every number in the range 1..n/2 will automatically be covered if all numbers in (n/2, n] exist. Instead of checking every integer, iterate only from n down to n/2 + 1. Convert each value to binary and verify its presence in s. This cuts the search space roughly in half while preserving correctness. The solution still depends on substring matching but reduces the number of checks significantly.
Binary conversion and substring scanning are the main operations, which makes this problem primarily about efficient string handling with a small mathematical observation on binary ranges. Understanding how binary prefixes propagate across numbers is the key insight.
Recommended for interviews: The optimized range check is what most interviewers expect. Starting with the brute-force iterative check shows that you understand the requirement clearly. Then introducing the n/2 observation demonstrates problem-solving skill and familiarity with binary properties, which is the differentiator in interviews.
This approach involves iterating through each number from 1 to n, converting it to its binary form, and checking if this binary string is a substring of s.
The function iterates over numbers from 1 to n, converts each number to a binary string using Python's builtin bin function, and checks if the resulting binary string (excluding the first two characters '0b') is a substring of s. If any number is not found, it returns False. Otherwise, it returns True after checking all numbers.
Time Complexity: O(n * m), where m is the maximum length of binary representation of numbers in range 1 to n.
Space Complexity: O(1), since we use a constant amount of extra space.
This approach involves checking only a part of range [1, n] by evaluating the length of s and maximum numbers that could be represented up to given s length.
This Python function limits necessary checks by only testing up to the minimum of n or 2^length of s, ensuring efficiency by narrowing the range based on possible binary length in s.
Time Complexity: O(min(n, 2^length(s)) * log(n)).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Iterative Binary Check | Time Complexity: O(n * m), where m is the maximum length of binary representation of numbers in range 1 to n. |
| Extend Range Check | Time Complexity: O(min(n, 2^length(s)) * log(n)). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Binary Check | O(n * |s|) | O(log n) | Simple baseline approach when constraints are small or when demonstrating the direct interpretation of the problem. |
| Extend Range Check | O((n/2) * |s|) | O(log n) | Preferred solution for interviews and larger inputs since it reduces the number of substring checks using a binary range observation. |
1016. Binary String With Substrings Representing 1 To N (Leetcode Medium) • Programming Live with Larry • 894 views views
Watch 8 more video solutions →Practice Binary String With Substrings Representing 1 To N with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor