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.

Description Hints 1 Solution Video 16:53

1016. Binary String With Substrings Representing 1 To N

Medium58.5% acceptance2 companies

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 <= 1000
s[i] is either '0' or '1'.
1 <= n <= 10⁹

Asked at 2 companies

Gartner

Google

Topics

String

Hints open one at a time

Hint 1

We only need to check substrings of length at most 30, because 10^9 has 30 bits.

16:53

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def queryString(self, s: str, n: int) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"0110"
3

Input

"0110"
4

Your code is saved on this device.Solution