Leetcode 1016. Binary String With Substrings Representing 1 To N
Problem Explanation
This problem is based on the concept of binary numbers and strings, and also touches upon substring manipulation in strings.
We are given a binary string S
and a positive integer N
. The binary string S
consists only of '0's and '1's.
Our task is to check whether the binary representation of every integer from 1 to N
is a substring of the given binary string S
.
A substring is a contiguous sequence of characters within a string. For example, in the string "abcdef", some of the substrings are "abc", "de", "f", "bcd" etc.
We need to return true if for every integer X
from 1 to N
, the binary representation of X
is a substring of S
. Otherwise, we return false.
Example
Input:
S = "0110"
N = 3
Explanation:
In this example, we see that the binary representations of the numbers from 1 to 3 are '1', '10', and '11' respectively. If we look at the string S
, we can see all of these binary numbers are present as substrings in S
.
Output:
true
Solution Approach
This approach is based on the concept of binary bitset and string manipulation.
In the provided solution, we are running a loop from n
to n/2
, for each iteration we are converting the integer i
to its binary representation using bitset
and storing it in binary
. The binary number is then reduced to remove leading zeros. After generating the binary representation, the solution checks if this binary is a substring in S
. If at any point, the solution finds a number for which the binary representation isn't in S
, it immediately returns false
. If it doesn't find such a number after looping from n
to n/2
, it ends the loop and returns true
.
Solution Python
1 2python 3class Solution: 4 def queryString(self, s: str, n: int) -> bool: 5 for i in range(n, n//2, -1): 6 binary = bin(i)[2:] #Converting integer to binary 7 if binary not in s: 8 return False 9 return True
Solution JavaScript
In JavaScript, we will use a similar approach. In place of the bin
function that python provides, we can use JavaScript's toString(2)
function to convert integers to binary representation.
Here is the code for JavaScript:
1
2javascript
3var queryString = function(s, n) {
4 for(let i = n; i > n/2; i--){
5 let binary = (i).toString(2);
6 if(!s.includes(binary)){
7 return false;
8 }
9 }
10 return true;
11};
Solution Java
In Java, we can use the built-in function Integer.toBinaryString(i)
to convert integers to their binary representation. We will also use a StringBuilder
to build and manipulate strings since they are mutable in Java unlike normal Strings.
1
2java
3class Solution {
4 public boolean queryString(String S, int N) {
5 for (int i = N; i > N / 2; i--) {
6 String binary = Integer.toBinaryString(i);
7 if (!S.contains(binary)) {
8 return false;
9 }
10 }
11 return true;
12 }
13}
Here, we go from N
to N/2
and for each i
, we convert it to its binary representation and check if it's a substring in S
.
In these solutions, time complexity is O(N) because in the worst-case scenario we go through each number from N
to N/2
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.