Jobs

Interviews

Discussions

Generate Binary Strings Without Adjacent Zeros

Medium

Amazon

3 views

Topics:

StringsRecursion

You are given a positive integer n.

A binary string x is valid if all substrings of x of length 2 contain at least one "1".

Return all valid strings with length n, in any order.

Example 1:

Input: n = 3 Output: ["010","011","101","110","111"]

Example 2:

Input: n = 1 Output: ["0","1"]

Explain how you would generate all valid binary strings with a length of n. Explain your approach, time complexity, and space complexity.

Generate Binary Strings Without Adjacent Zeros

Medium

Amazon

3 views

Topics:

StringsRecursion

You are given a positive integer n.

A binary string x is valid if all substrings of x of length 2 contain at least one "1".

Return all valid strings with length n, in any order.

Example 1:

Input: n = 3 Output: ["010","011","101","110","111"]

Example 2:

Input: n = 1 Output: ["0","1"]

Explain how you would generate all valid binary strings with a length of n. Explain your approach, time complexity, and space complexity.

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 desired length, `n`, of the binary strings to be generated? What are the possible constraints on `n` (e.g., is it always a positive integer, is there a maximum value)?
If `n` is zero, should I return an empty list, or is that an invalid input?
Do you want me to return a list of strings, or is there a specific format you would prefer for the output?
Is the order of the generated strings in the output important, or can they be in any order?
Are there any specific memory constraints or performance considerations besides generating the strings efficiently?

Brute Force Solution

Approach

We need to create binary strings (strings made of 0s and 1s) of a specific length, but no two 0s can be next to each other. The brute force way is to try absolutely every possible combination of 0s and 1s of that length, and then check if each one follows the rule.

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

Start with the very first possible binary string of the correct length (all zeros or all ones, for example).
Check if that string has any adjacent zeros. If it does, throw it out.
If it does not have adjacent zeros, keep it as a valid string.
Move to the next possible binary string (like counting in binary).
Again, check if the new string has adjacent zeros. If yes, discard it.
If it's valid, save it.
Keep repeating this process, going through every single possible binary string of the given length.
When you are done, you will have a list of all the binary strings that meet the rule.

Code Implementation

def generate_binary_strings_brute_force(string_length):
    valid_strings = []
    number_of_possible_strings = 2 ** string_length

    for i in range(number_of_possible_strings):
        # Convert the integer to its binary representation
        binary_string = bin(i)[2:].zfill(string_length)

        # Check for adjacent zeros
        if not has_adjacent_zeros(binary_string):

            #If no adjacent zeros, add to result
            valid_strings.append(binary_string)

    return valid_strings

def has_adjacent_zeros(binary_string):
    # Iterate through the string and check for adjacent 0s
    for i in range(len(binary_string) - 1):

        #This is the crucial step of the logic
        if binary_string[i] == '0' and binary_string[i+1] == '0':
            return True

    return False

Big(O) Analysis

Time Complexity

O(2^n * n) – The algorithm iterates through all possible binary strings of length n. There are 2^n such strings. For each string, it checks for adjacent zeros. This check requires iterating through the string of length n. Therefore, the overall time complexity is O(2^n * n).

Space Complexity

O(2^N) – The brute force approach, as described, generates every possible binary string of length N. Each of these strings is stored temporarily to be checked. In the worst-case, all 2^N possible strings are valid and need to be saved, resulting in a list of size 2^N. This list represents the auxiliary space used, thus making the space complexity O(2^N).

Optimal Solution

Approach

We'll construct our binary strings piece by piece, ensuring no adjacent zeros appear. The core idea is to keep track of the last digit we added and intelligently choose the next one, making sure we don't break the rule.

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

Begin by creating strings one digit at a time.
For the very first digit, you can start with either a zero or a one.
Now, for each following digit, consider the last digit you used.
If the last digit was a one, you can add either a zero or a one as the next digit.
However, if the last digit was a zero, you *must* add a one as the next digit to avoid adjacent zeros.
Continue adding digits in this way, always checking the last digit before deciding on the next one.
Each time you build a string of the desired length, add it to your list of valid binary strings.
By following this decision-making process, you build up valid combinations without having to try every single possible combination.

Code Implementation

def generate_binary_strings_without_adjacent_zeros(string_length):
    result = []

    def generate(current_string, last_digit):
        if len(current_string) == string_length:
            result.append(current_string)
            return

        # If the last digit was '1', we can add '0' or '1'
        if last_digit == '1' or last_digit is None:
            generate(current_string + '0', '0')

            generate(current_string + '1', '1')

        # If the last digit was '0', we must add '1'
        elif last_digit == '0':
            generate(current_string + '1', '1')

    # Start generation with both '0' and '1' as initial digits.
    generate('0', '0')
    
    generate('1', '1')
    
    return result

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm explores all possible binary strings of length n where adjacent zeros are not allowed. In the worst-case scenario, it generates a significant portion of all possible binary strings, even though it prunes some branches. The number of valid binary strings without adjacent zeros grows exponentially with n, approaching a Fibonacci sequence, which itself exhibits exponential growth. Therefore, the time complexity is dominated by the generation of these strings, leading to a time complexity of O(2^n).

Space Complexity

O(N) – The space complexity is primarily determined by the storage of the generated binary strings. As the algorithm builds strings of length N and adds them to a list, the size of this list can grow proportionally to the number of valid strings, which, in the worst case, could be exponential. However, the plain english description mentions adding strings to a list *each time we build a string of the desired length*. The number of generated strings could grow exponentially, but the length of each string is N. Since the algorithm builds and stores strings of length N and the number of strings is considered constant for the space complexity (since the algorithm focuses on building valid binary strings of N length, not storing all strings of length < N), the space used grows linearly with N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Input n is 0	Return an empty string list as there are no binary strings of length 0.
Input n is 1	Return a list containing '0' and '1' as these are the only valid strings.
Large n value	Be mindful of exponential growth in the number of strings generated and potential memory constraints if storing all strings.
n is a negative integer	Throw an IllegalArgumentException or return an empty list, indicating invalid input.
Recursive solution stack overflow with very large n	Consider using an iterative approach to avoid stack overflow for large inputs.
Memory limits exceeded when storing intermediate results for larger n.	Consider printing or streaming the results instead of storing them all in memory.
All binary strings starting with '0' will have limited application	Consider an option to filter the results further when applicable.
Outputting strings vs numbers.	Ensure your numbers do not have leading zeroes in the output or in the strings generated if you are converting from numerical representation, as '01' has no mathematical meaning when representing a number.

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 desired length, `n`, of the binary strings to be generated? What are the possible constraints on `n` (e.g., is it always a positive integer, is there a maximum value)?
If `n` is zero, should I return an empty list, or is that an invalid input?
Do you want me to return a list of strings, or is there a specific format you would prefer for the output?
Is the order of the generated strings in the output important, or can they be in any order?
Are there any specific memory constraints or performance considerations besides generating the strings efficiently?

Brute Force Solution

Approach

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

Start with the very first possible binary string of the correct length (all zeros or all ones, for example).
Check if that string has any adjacent zeros. If it does, throw it out.
If it does not have adjacent zeros, keep it as a valid string.
Move to the next possible binary string (like counting in binary).
Again, check if the new string has adjacent zeros. If yes, discard it.
If it's valid, save it.
Keep repeating this process, going through every single possible binary string of the given length.
When you are done, you will have a list of all the binary strings that meet the rule.

Code Implementation

def generate_binary_strings_brute_force(string_length):
    valid_strings = []
    number_of_possible_strings = 2 ** string_length

    for i in range(number_of_possible_strings):
        # Convert the integer to its binary representation
        binary_string = bin(i)[2:].zfill(string_length)

        # Check for adjacent zeros
        if not has_adjacent_zeros(binary_string):

            #If no adjacent zeros, add to result
            valid_strings.append(binary_string)

    return valid_strings

def has_adjacent_zeros(binary_string):
    # Iterate through the string and check for adjacent 0s
    for i in range(len(binary_string) - 1):

        #This is the crucial step of the logic
        if binary_string[i] == '0' and binary_string[i+1] == '0':
            return True

    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin by creating strings one digit at a time.
For the very first digit, you can start with either a zero or a one.
Now, for each following digit, consider the last digit you used.
If the last digit was a one, you can add either a zero or a one as the next digit.
However, if the last digit was a zero, you *must* add a one as the next digit to avoid adjacent zeros.
Continue adding digits in this way, always checking the last digit before deciding on the next one.
Each time you build a string of the desired length, add it to your list of valid binary strings.
By following this decision-making process, you build up valid combinations without having to try every single possible combination.

Code Implementation

def generate_binary_strings_without_adjacent_zeros(string_length):
    result = []

    def generate(current_string, last_digit):
        if len(current_string) == string_length:
            result.append(current_string)
            return

        # If the last digit was '1', we can add '0' or '1'
        if last_digit == '1' or last_digit is None:
            generate(current_string + '0', '0')

            generate(current_string + '1', '1')

        # If the last digit was '0', we must add '1'
        elif last_digit == '0':
            generate(current_string + '1', '1')

    # Start generation with both '0' and '1' as initial digits.
    generate('0', '0')
    
    generate('1', '1')
    
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 0	Return an empty string list as there are no binary strings of length 0.
Input n is 1	Return a list containing '0' and '1' as these are the only valid strings.
Large n value	Be mindful of exponential growth in the number of strings generated and potential memory constraints if storing all strings.
n is a negative integer	Throw an IllegalArgumentException or return an empty list, indicating invalid input.
Recursive solution stack overflow with very large n	Consider using an iterative approach to avoid stack overflow for large inputs.
Memory limits exceeded when storing intermediate results for larger n.	Consider printing or streaming the results instead of storing them all in memory.
All binary strings starting with '0' will have limited application	Consider an option to filter the results further when applicable.
Outputting strings vs numbers.	Ensure your numbers do not have leading zeroes in the output or in the strings generated if you are converting from numerical representation, as '01' has no mathematical meaning when representing a number.