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.
- Difficulty: Medium
- Topics: Strings, Hash Table, Bit Manipulation, Sliding Window
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000s[i] is either '0' or '1'1 <= n <= 10^9
Hints for Binary String With Substrings Representing 1 To N
Hint 1
If the binary form of
xoccurs ins, so does the binary form ofx / 2— it is a prefix of it. So only numbers greater thann / 2need checking.Hint 2
A string of length
Lhas at mostL - k + 1distinct substrings of lengthk. Ifnis large, the numbers in(n / 2, n]cannot all fit.Hint 3
So check
xfromndown ton / 2 + 1and stop at the first one missing — the loop either ends quickly withfalseornis 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
- For
xfromndown tofloor(n / 2) + 1, writexin binary. - If that binary string is not a substring of
s, returnfalse. - 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 ofx)
Pitfalls
- Looping all the way from 1 to
nis fine only because of the early exit; never build a set of allnnumbers whennis 10^9. - Binary forms have no leading zeros, but
smay 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 TrueJava
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