Binary String With Substrings Representing 1 To N

Medium
1748.

Binary String With Substrings Representing 1 To N

Binary String With Substrings Representing 1 To N is a medium coding problem on strings, hash table and bit manipulation, asked in Google interviews.

Given a binary string s and a positive integer n, return true if, for every integer x in the range [1, n], the binary representation of x (without leading zeros) appears as a substring of s. Otherwise return false.

Example 1

Input
s = "1101", n = 3
Output
true
Explanation
`1` = "1", `2` = "10" and `3` = "11" all occur in `"1101"`.

Example 2

Input
s = "1101", n = 4
Output
false
Explanation
`4` = "100" does not occur.

Example 3

Input
s = "1", n = 1000000000
Output
false

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'
  • 1 <= n <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} n
 * @return {boolean}
 */
var queryString = function(s, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary String With Substrings Representing 1 To N — Solution

Binary String With Substrings Representing 1 To N solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Binary String With Substrings Representing 1 To N is a medium coding problem on strings, hash table and bit manipulation, asked in Google interviews.

Problem statement

Given a binary string s and a positive integer n, return true if, for every integer x in the range [1, n], the binary representation of x (without leading zeros) appears as a substring of s. Otherwise return false.

Example 1

Input: s = "1101", n = 3
Output: true
Explanation: `1` = "1", `2` = "10" and `3` = "11" all occur in `"1101"`.

Example 2

Input: s = "1101", n = 4
Output: false
Explanation: `4` = "100" does not occur.

Example 3

Input: s = "1", n = 1000000000
Output: false

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'
  • 1 <= n <= 10^9

Hints for Binary String With Substrings Representing 1 To N

  1. Hint 1

    If the binary form of x occurs in s, so does the binary form of x / 2 — it is a prefix of it. So only numbers greater than n / 2 need checking.

  2. Hint 2

    A string of length L has at most L - k + 1 distinct substrings of length k. If n is large, the numbers in (n / 2, n] cannot all fit.

  3. Hint 3

    So check x from n down to n / 2 + 1 and stop at the first one missing — the loop either ends quickly with false or n is small.

How to solve Binary String With Substrings Representing 1 To N

Only the upper half of the range matters (every smaller number is a prefix of a number in it), and that half fails fast once n is large, so a direct substring check of each number in (n/2, n] is efficient.

Approach

  1. For x from n down to floor(n / 2) + 1, write x in binary.
  2. If that binary string is not a substring of s, return false.
  3. If the loop finishes, return true.

Why it works

For x <= n / 2, the binary form of 2x is the binary form of x followed by 0, and 2x lies in (n/2, n] after doubling enough times; so if all of the upper half occurs, everything does. Every number in the upper half has one of at most two bit lengths, and s has at most 1000 distinct substrings of each length, so when the half holds more than about 2000 numbers some are missing — the loop meets one within roughly 2000 checks.

Complexity

  • Time — O(min(n, |s|) · |s|) substring checks of strings up to 30 characters
  • Space — O(1) extra (the binary string of x)

Pitfalls

  • Looping all the way from 1 to n is fine only because of the early exit; never build a set of all n numbers when n is 10^9.
  • Binary forms have no leading zeros, but s may contain zeros anywhere.

Reference solution

Python

def queryString(s: str, n: int) -> bool:
    for x in range(n, n // 2, -1):
        if bin(x)[2:] not in s:
            return False
    return True

Java

public static boolean queryString(String s, int n) {
    for (int x = n; x > n / 2; x--) {
        if (!s.contains(Integer.toBinaryString(x))) return false;
    }
    return true;
}

C++

bool queryString(string s, int n) {
    for (int x = n; x > n / 2; x--) {
        string b;
        for (int v = x; v > 0; v >>= 1) b += (char) ('0' + (v & 1));
        reverse(b.begin(), b.end());
        if (s.find(b) == string::npos) return false;
    }
    return true;
}

JavaScript

var queryString = function(s, n) {
    for (var x = n; x > Math.floor(n / 2); x--) {
        if (s.indexOf(x.toString(2)) === -1) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets