Binary String With Substrings Representing 1 To N - Leetcode Solution

Problem statement:

Given a binary string S (a string consisting only of '0' and '1's) and a positive integer N, return true if and only if for every integer X from 1 to N, the binary representation of X is a substring of S.

Example 1:

Input: S = "0110", N = 3 Output: true

Example 2:

Input: S = "0110", N = 4 Output: false

Solution:

To solve this problem we can use the sliding window approach, where we start with a window of length 1 and then keep on increasing the window size until we reach N. For each window, we check if the binary representation of the current number is present in the given binary string S. If it is not present then we move the window forward by one and check again.

Algorithm:

1. Convert the given binary string S to an integer value.
2. Create a set called "substrings" to store all the possible binary representations of integers from 1 to N.
3. Initiate a loop from 1 to N.
4. Convert the current integer to its binary representation using the bin() function, remove the prefix "0b" and add it to the "substrings" set.
5. Start with a window of length 1 and move the window forward until it includes all the strings in the "substrings" set.
6. If any of the string is not found in the given binary string S, return False.
7. If all the strings are found, return True.

Python code:

def queryString(S: str, N: int) -> bool: substrings = set() S_int = int(S, 2) for i in range(1, N+1): substrings.add(bin(i)[2:]) for length in range(1, len(S)+1): for start in range(len(S)-length+1): num = int(S[start:start+length], 2) if num in range(1, N+1): substrings.discard(bin(num)[2:]) if not substrings: return True return False

Time complexity:

In the worst case, we have to check all the substrings of the given binary string S, which takes O(n^2) time. The conversion of integers to binary and addition to the set takes O(n log n) time. Hence, the overall time complexity of the algorithm is O(n^2 + n log n) which is equivalent to O(n^2).

Space complexity:

The space complexity of the algorithm is O(n log n) to store the possible binary representations of integers from 1 to N.

1