Binary String With Substrings Representing 1 To N solution and explanation
Google
8 more videos on this problem
1016. Binary String With Substrings Representing 1 To N (Leetcode Medium)Programming Live with Larry · 16:53 · 915 views
Binary String With Substrings Representing 1 To N || LeetCode solution || medium problemRishabh Gaur · 19:04 · 902 views
Binary String With Substrings Representing 1 To N | LeetCodeKnowledge Amplifier · 1:36 · 893 views
猩猩的乐园 Leetcode 1016 Binary String With Substrings Representing 1 To N猩猩的乐园 · 7:48 · 365 views
Binary String With Substrings 1 to N | Leetcode 1016 | Python Solution in Telugu | srkcodesSrk Codes · 18:11 · 227 views
Leetcode 1016. Binary String With Substrings Representing 1 To N (sliding window)LetsCode · 5:20 · 142 views
06| Leetcode |Bomb diffuse with negative key | Binary String With Substrings Representing 1 To NTechi Sugan · 1:26:18 · 109 views
No Sound Leetcode 1016: Binary String with Substrings Representing 1 To NExtremeProgrammer · 1:05 · 24 views
LeetCode 1016: Binary String With Substrings Representing 1 To NAlitaCode · 26:13 · 15 views
The problem
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 <= 109
Approach overview
Problem 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.
Approach 1: Iterative Binary Check
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.
def query_string(s: str, n: int) -> bool:
for num in range(1, n + 1):
binary_rep = bin(num)[2:]
if binary_rep not in s:
return False
return Truepublic class Solution {
public boolean queryString(String s, int n) {
for (int i = 1; i <= n; i++) {
String binary = Integer.toBinaryString(i);
if (!s.contains(binary)) {
return false;
}
}
return true;
}
}#include <string>
using namespace std;
bool queryString(string s, int n) {
for (int i = 1; i <= n; ++i) {
string binary = bitset<32>(i).to_string();
binary = binary.substr(binary.find('1'));
if (s.find(binary) == string::npos) {
return false;
}
}
return true;
}function queryString(s, n) {
for (let i = 1; i <= n; i++) {
const binary = i.toString(2);
if (!s.includes(binary)) {
return false;
}
}
return true;
}#include <string.h>
#include <stdio.h>
#include <stdbool.h>
bool queryString(char* s, int n) {
char binary[32];
for (int i = 1; i <= n; i++) {
snprintf(binary, sizeof(binary), "%b", i);
if (strstr(s, binary) == NULL) {
return false;
}
}
return true;
}public class Solution {
public bool QueryString(string s, int n) {
for (int i = 1; i <= n; i++) {
string binary = Convert.ToString(i, 2);
if (!s.Contains(binary)) {
return false;
}
}
return true;
}
}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.
Approach 2: Extend Range Check
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.
def query_string(s: str, n: int) -> bool:
max_check = min(n, 2 ** len(s))
for num in range(1, max_check + 1):
binary_rep = bin(num)[2:]
if binary_rep not in s:
return False
return Truepublic class Solution {
public boolean queryString(String s, int n) {
int maxCheck = Math.min(n, 1 << s.length());
for (int i = 1; i <= maxCheck; i++) {
String binary = Integer.toBinaryString(i);
if (!s.contains(binary)) {
return false;
}
}
return true;
}
}#include <string>
#include <algorithm>
using namespace std;
bool queryString(string s, int n) {
int max_check = min(n, (1 << s.length()));
for (int i = 1; i <= max_check; ++i) {
string binary = bitset<32>(i).to_string();
binary = binary.substr(binary.find('1'));
if (s.find(binary) == string::npos) {
return false;
}
}
return true;
}function queryString(s, n) {
const maxCheck = Math.min(n, Math.pow(2, s.length));
for (let i = 1; i <= maxCheck; i++) {
const binary = i.toString(2);
if (!s.includes(binary)) {
return false;
}
}
return true;
}#include <string.h>
#include <stdio.h>
#include <stdbool.h>
bool queryString(char* s, int n) {
int maxCheck = n < (1 << strlen(s)) ? n : (1 << strlen(s));
char binary[32];
for (int i = 1; i <= maxCheck; i++) {
snprintf(binary, sizeof(binary), "%b", i);
if (strstr(s, binary) == NULL) {
return false;
}
}
return true;
}public class Solution {
public bool QueryString(string s, int n) {
int maxCheck = Math.Min(n, 1 << s.Length);
for (int i = 1; i <= maxCheck; i++) {
string binary = Convert.ToString(i, 2);
if (!s.Contains(binary)) {
return false;
}
}
return true;
}
}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 3: Brain Teaser
We observe that the length of string s does not exceed 1000, so string s can represent at most 1000 binary integers. Therefore, if n \gt 1000, then s definitely cannot represent the binary representation of all integers in the range [1,.. n].
Additionally, for an integer x, if the binary representation of x is a substring of s, then the binary representation of \lfloor x / 2 \rfloor is also a substring of s. Therefore, we only need to check whether the binary representations of integers in the range [\lfloor n / 2 \rfloor + 1,.. n] are substrings of s.
The time complexity is O(m^2 times log m) and the space complexity is O(log n), where m is the length of string s and n is the positive integer given in the problem.
function queryString(s: string, n: number): boolean {
if (n > 1000) {
return false;
}
for (let i = n; i > n / 2; --i) {
if (s.indexOf(i.toString(2)) === -1) {
return false;
}
}
return true;
}func queryString(s string, n int) bool {
if n > 1000 {
return false
}
for i := n; i > n/2; i-- {
if !strings.Contains(s, strconv.FormatInt(int64(i), 2)) {
return false
}
}
return true
}func queryString(s string, n int) bool {
if n > 1000 {
return false
}
for i := n; i > n/2; i-- {
if !strings.Contains(s, strconv.FormatInt(int64(i), 2)) {
return false
}
}
return true
}Complexity comparison
| 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)). |
| Brain Teaser | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Binary String With Substrings Representing 1 To N easy or hard?
Binary String With Substrings Representing 1 To N is rated Medium difficulty. The implementation is straightforward, but recognizing that only numbers greater than n/2 must be checked requires deeper reasoning about binary representations and substring coverage.
Binary String With Substrings Representing 1 To N Python/Java solution
In Python or Java, the common approach converts each integer to binary using built-in utilities such as bin(i)[2:] in Python or Integer.toBinaryString(i) in Java. Each binary string is then searched inside s using contains or find operations. Applying the n/2 optimization keeps the number of checks manageable.
How to solve Binary String With Substrings Representing 1 To N in O(n)?
A strict O(n) solution is difficult with straightforward substring checks because each search may scan the string. Some optimized implementations use hashing or substring indexing to speed up lookups, but most accepted solutions rely on O(n log n) or O(n * |s|) substring checks with the n/2 optimization.
What is the best approach for Binary String With Substrings Representing 1 To N?
The optimized range check approach is the most practical solution. Instead of checking every integer from 1 to n, only numbers from n down to n/2 + 1 are verified. If those larger binary values appear as substrings, the smaller ones are guaranteed to appear as well. This reduces the number of substring searches while keeping the implementation simple.
Is Binary String With Substrings Representing 1 To N asked at Google/Amazon/Meta?
This problem reflects the type of string and binary reasoning questions commonly used in interviews at companies like Google, Amazon, and Meta. It tests substring search, binary representation, and the ability to recognize mathematical constraints that reduce brute-force work.
What data structure is used in Binary String With Substrings Representing 1 To N?
The core structure used is a string for substring search. The algorithm repeatedly generates binary strings and checks whether they exist inside the main string using built-in search functions. Some optimized variants may use sets or hashing to speed up substring checks.
What is the time complexity of Binary String With Substrings Representing 1 To N?
The typical solution runs in O(n * |s|) time because each number is converted to binary and searched inside the string. With the range optimization that checks only numbers greater than n/2, the effective work becomes roughly O((n/2) * |s|). Space complexity is O(log n) due to storing binary representations.