Jobs

Interviews

Discussions

Binary String With Substrings Representing 1 To N

Medium

Asked by:

7 views

Topics:

Strings

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⁹

Try coding it in LeetCode

Binary String With Substrings Representing 1 To N

Medium

Asked by:

7 views

Topics:

Strings

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⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `N`? This will help determine the length of the required binary string.
Can I assume `N` will always be a positive integer greater than or equal to 1?
If a binary string containing substrings from 1 to `N` doesn't exist, what should I return (e.g., `null`, an empty string, or an error)?
By 'substring,' do you mean a contiguous sequence of characters within the binary string, or are there any other interpretations I should consider?
Do the binary representations of the numbers 1 to N need to be distinct substrings within the larger binary string?

Brute Force Solution

Approach

The brute-force approach means checking if our big string contains the binary representation of every number from 1 to our target number N. We will generate the binary representation for each number and then check to see if it is a substring of the given string.

Here's how the algorithm would work step-by-step:

Start with the number 1.
Find the binary representation of this number.
Check if the big string contains this binary representation.
Move on to the next number, 2.
Find the binary representation of 2.
Check if the big string contains the binary representation of 2.
Keep doing this for every number, one by one, all the way up to the target number N.
If, at any point, you find a number whose binary representation is NOT in the big string, you know the answer is no.
If you get through all the numbers from 1 to N, and every number's binary representation is in the big string, then the answer is yes.

Code Implementation

def string_contains_binary_numbers(
    big_string: str, target_number: int) -> bool:

    for current_number in range(1, target_number + 1):
        # Convert the current number to its binary string representation
        binary_representation =
            bin(current_number)[2:]

        # Check if the binary string is a substring of the big string
        if binary_representation not in big_string:
            # If not a substring, then we can stop and return false
            return False

    # If all binary representations were found, return true
    return True

Big(O) Analysis

Time Complexity

O(NlogN) – The algorithm iterates from 1 to N. Inside the loop, the binary representation of each number 'i' is generated, which takes O(log i) time, as the length of the binary representation is proportional to log i. Then, we check if the given string contains this binary string which takes O(S) where S is the size of given string. Therefore the outer loop from 1 to N takes (O(S) + O(log1) + O(S) + O(log2) + ... + O(S) + O(logN) or N * O(S) + O(log1 + log2 + ... logN). S is a constant so that becomes N + O(log(N!)). Since log(N!) is approximately NlogN the dominant factor is NlogN, yielding a time complexity of O(NlogN).

Space Complexity

O(log N) – The described brute-force approach iteratively converts numbers from 1 to N into their binary string representation. The maximum length of the binary string for a number up to N is log2(N) (or simply log N). Since we generate one binary string at a time and check for its presence as a substring, the space used is dominated by the largest possible binary string which is proportional to log N. Other variables used like loop counters take constant space. Therefore, the auxiliary space complexity is O(log N).

Optimal Solution

Approach

The core idea is to check if all the binary representations of numbers from 1 to N are present as substrings within the given binary string. We can efficiently accomplish this by systematically generating all such binary representations and verifying their presence. This avoids complex search algorithms.

Here's how the algorithm would work step-by-step:

Calculate the binary representation for each number from 1 up to N.
For each binary representation you generated, check if it's contained within the larger given binary string.
If all binary representations from 1 to N are found within the larger string, then the answer is 'yes'.
Otherwise, if even one binary representation is missing, the answer is 'no'.

Code Implementation

def string_contains_binary_codes(binary_string, number):
    for integer in range(1, number + 1):

        binary_representation = bin(integer)[2:]

        # Check if the binary representation is a substring.
        if binary_representation not in binary_string:
            return False

    return True

def is_substring(main_string, sub_string):
    #Check if substring is within mainstring
    return sub_string in main_string

def binary_string_contains_substrings(binary_string, number):
    # Iterate from 1 to the input number.
    for integer in range(1, number + 1):
        # Convert the integer to its binary string representation.
        binary_representation = bin(integer)[2:]

        # Check if the binary representation is a substring of the main string.
        # If not, return False immediately.
        if not is_substring(binary_string, binary_representation):
            return False

    # If all binary representations are found, return True.
    return True

def check_binary_string_contains_substrings(binary_string, number):
    # Iterate through numbers to check their binary representations
    for integer in range(1, number + 1):

        binary_representation = bin(integer)[2:]
        
        # This is the core logic to determine if each binary
        # representation is a substring within the binary string.
        if binary_representation not in binary_string:
            return False

    # All binary representations were found.
    return True

Big(O) Analysis

Time Complexity

O(n*log(n)*m) – The algorithm iterates from 1 to n. Inside the loop, converting a number i to its binary string representation takes O(log(i)) time, which is effectively O(log(n)) in the worst case. Subsequently, the algorithm checks if this binary string is a substring of the given string, s, of length m. This substring search operation has a time complexity of O(m). Therefore, the overall time complexity is approximately O(n * log(n) * m), where n is the input integer and m is the length of the input binary string.

Space Complexity

O(log N) – The dominant space usage stems from generating the binary representations of numbers from 1 to N. The maximum length of a binary representation for a number up to N is log2(N). In the worst case, we might store these binary representations temporarily, which consumes space proportional to the length of the longest binary string. Therefore, the space complexity is O(log N).

Edge Cases

Case	How to Handle
Empty string s or n = 0	Return true immediately because any substring can be found in an empty string if n is zero
n is larger than the maximum possible number representable by a substring of s given s's length	Calculate the maximum possible number for a given substring length in s and return false if n is bigger than that
s is shorter than the minimum length required to contain substrings representing 1 to n	Return false because the string can't possibly contain all required substrings.
n is a very large number causing possible integer overflow if not handled correctly	Use long or appropriate data type to prevent overflow while checking substrings
s contains characters other than '0' and '1'	Throw an IllegalArgumentException or return false because the input string is invalid
s consists only of '0' characters and n is not 0	Return false because the string can only represent 0 and nothing higher than 0
n = 1 and s is an empty string	Return false since even representing '1' is impossible in an empty string
The solution is time-complexity inefficient and results in Time Limit Exceeded for large s and n	Optimize the substring search or use a rolling hash to improve the performance

Empty string s or n = 0

How to Handle:

Return true immediately because any substring can be found in an empty string if n is zero

n is larger than the maximum possible number representable by a substring of s given s's length

How to Handle:

Calculate the maximum possible number for a given substring length in s and return false if n is bigger than that

s is shorter than the minimum length required to contain substrings representing 1 to n

How to Handle:

Return false because the string can't possibly contain all required substrings.

n is a very large number causing possible integer overflow if not handled correctly

How to Handle:

Use long or appropriate data type to prevent overflow while checking substrings

s contains characters other than '0' and '1'

How to Handle:

Throw an IllegalArgumentException or return false because the input string is invalid

s consists only of '0' characters and n is not 0

How to Handle:

Return false because the string can only represent 0 and nothing higher than 0

n = 1 and s is an empty string

How to Handle:

Return false since even representing '1' is impossible in an empty string

The solution is time-complexity inefficient and results in Time Limit Exceeded for large s and n

How to Handle:

Optimize the substring search or use a rolling hash to improve the performance

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `N`? This will help determine the length of the required binary string.
Can I assume `N` will always be a positive integer greater than or equal to 1?
If a binary string containing substrings from 1 to `N` doesn't exist, what should I return (e.g., `null`, an empty string, or an error)?
By 'substring,' do you mean a contiguous sequence of characters within the binary string, or are there any other interpretations I should consider?
Do the binary representations of the numbers 1 to N need to be distinct substrings within the larger binary string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1.
Find the binary representation of this number.
Check if the big string contains this binary representation.
Move on to the next number, 2.
Find the binary representation of 2.
Check if the big string contains the binary representation of 2.
Keep doing this for every number, one by one, all the way up to the target number N.
If, at any point, you find a number whose binary representation is NOT in the big string, you know the answer is no.
If you get through all the numbers from 1 to N, and every number's binary representation is in the big string, then the answer is yes.

Code Implementation

def string_contains_binary_numbers(
    big_string: str, target_number: int) -> bool:

    for current_number in range(1, target_number + 1):
        # Convert the current number to its binary string representation
        binary_representation =
            bin(current_number)[2:]

        # Check if the binary string is a substring of the big string
        if binary_representation not in big_string:
            # If not a substring, then we can stop and return false
            return False

    # If all binary representations were found, return true
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate the binary representation for each number from 1 up to N.
For each binary representation you generated, check if it's contained within the larger given binary string.
If all binary representations from 1 to N are found within the larger string, then the answer is 'yes'.
Otherwise, if even one binary representation is missing, the answer is 'no'.

Code Implementation

def string_contains_binary_codes(binary_string, number):
    for integer in range(1, number + 1):

        binary_representation = bin(integer)[2:]

        # Check if the binary representation is a substring.
        if binary_representation not in binary_string:
            return False

    return True

def is_substring(main_string, sub_string):
    #Check if substring is within mainstring
    return sub_string in main_string

def binary_string_contains_substrings(binary_string, number):
    # Iterate from 1 to the input number.
    for integer in range(1, number + 1):
        # Convert the integer to its binary string representation.
        binary_representation = bin(integer)[2:]

        # Check if the binary representation is a substring of the main string.
        # If not, return False immediately.
        if not is_substring(binary_string, binary_representation):
            return False

    # If all binary representations are found, return True.
    return True

def check_binary_string_contains_substrings(binary_string, number):
    # Iterate through numbers to check their binary representations
    for integer in range(1, number + 1):

        binary_representation = bin(integer)[2:]
        
        # This is the core logic to determine if each binary
        # representation is a substring within the binary string.
        if binary_representation not in binary_string:
            return False

    # All binary representations were found.
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string s or n = 0	Return true immediately because any substring can be found in an empty string if n is zero
n is larger than the maximum possible number representable by a substring of s given s's length	Calculate the maximum possible number for a given substring length in s and return false if n is bigger than that
s is shorter than the minimum length required to contain substrings representing 1 to n	Return false because the string can't possibly contain all required substrings.
n is a very large number causing possible integer overflow if not handled correctly	Use long or appropriate data type to prevent overflow while checking substrings
s contains characters other than '0' and '1'	Throw an IllegalArgumentException or return false because the input string is invalid
s consists only of '0' characters and n is not 0	Return false because the string can only represent 0 and nothing higher than 0
n = 1 and s is an empty string	Return false since even representing '1' is impossible in an empty string
The solution is time-complexity inefficient and results in Time Limit Exceeded for large s and n	Optimize the substring search or use a rolling hash to improve the performance

Empty string s or n = 0

How to Handle:

Return true immediately because any substring can be found in an empty string if n is zero

n is larger than the maximum possible number representable by a substring of s given s's length

How to Handle:

Calculate the maximum possible number for a given substring length in s and return false if n is bigger than that

s is shorter than the minimum length required to contain substrings representing 1 to n

How to Handle:

Return false because the string can't possibly contain all required substrings.

n is a very large number causing possible integer overflow if not handled correctly

How to Handle:

Use long or appropriate data type to prevent overflow while checking substrings

s contains characters other than '0' and '1'

How to Handle:

Throw an IllegalArgumentException or return false because the input string is invalid

s consists only of '0' characters and n is not 0

How to Handle:

Return false because the string can only represent 0 and nothing higher than 0

n = 1 and s is an empty string

How to Handle:

Return false since even representing '1' is impossible in an empty string

The solution is time-complexity inefficient and results in Time Limit Exceeded for large s and n

How to Handle:

Optimize the substring search or use a rolling hash to improve the performance