We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Generate Binary Strings Without Adjacent Zeros

Number: 3453

Difficulty: Medium

Paid? No

Companies: Google, Amazon

Problem Description

Given a positive integer n, generate all binary strings of length n such that every substring of length 2 contains at least one '1'. In other words, no string contains two consecutive '0's.

Key Insights

  • The only invalid scenario is when two adjacent '0's occur.
  • When constructing the string, if the last character is '0', the next character must be '1'.
  • Backtracking (or DFS) is an ideal approach to build the strings while enforcing the validity constraint.

Space and Time Complexity

Time Complexity: O(2^n) in the worst-case as each position may branch into 2 possibilities. Space Complexity: O(2^n * n) to store all valid strings and O(n) auxiliary space for recursion.

Solution

We solve the problem using a backtracking approach:

  1. Start with an empty string.
  2. At each step, append '0' or '1' based on the previous character:
    • If the string is empty or its last character is '1', both '0' and '1' can be appended.
    • If the last character is '0', only '1' can be added to avoid adjacent zeros.
  3. Once a string of length n is formed, add it to the results list.
  4. Return the list of all valid strings.

Data structures and techniques used:

  • Recursion for backtracking.
  • A list/array to collect valid strings.
  • Conditional checks to enforce the adjacency rule.

Code Solutions

# Python solution for generating valid binary strings without adjacent zeros.
def generateBinaryStrings(n: int) -> list:
    # List to store all valid binary strings.
    result = []
    
    # Recursive helper function for backtracking.
    def backtrack(current: str):
        # If the current string has reached length n, add to the result list.
        if len(current) == n:
            result.append(current)
            return
        # If the string is empty or ends with '1', both '0' and '1' can be appended.
        if not current or current[-1] == '1':
            backtrack(current + '0')
            backtrack(current + '1')
        else:
            # Last character is '0'; we must append '1' to avoid consecutive zeros.
            backtrack(current + '1')
    
    # Start backtracking with an empty string.
    backtrack("")
    return result

# Example usage:
if __name__ == "__main__":
    n = 3
    print(generateBinaryStrings(n))
← Back to All Questions