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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Generate Binary Strings Without Adjacent Zeros

Difficulty: Medium

Problem Description

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.

Key Insights

  • A valid binary string cannot have two consecutive '0's.
  • Any valid string can end with either '0' or '1', but if it ends with '0', the previous character must be '1'.
  • This problem can be approached using backtracking to generate all strings and filter out the invalid ones.

Space and Time Complexity

Time Complexity: O(2^n) - since every bit can be independently set to 0 or 1, leading to 2^n combinations. Space Complexity: O(n) - for the recursive stack and storing valid strings.

Solution

The solution employs a backtracking algorithm to construct valid binary strings recursively. Starting with an empty string, we add '0' or '1' based on the last character added:

  1. If the last character is '1', we can freely add either '0' or '1'.
  2. If the last character is '0', we can only add '1' to avoid two consecutive '0's.
  3. Once the string reaches the desired length n, it is added to the result list.

Code Solutions

def generateBinaryStrings(n):
    result = []
    
    def backtrack(current):
        if len(current) == n:
            result.append(current)
            return
        
        # Add '1' and continue
        backtrack(current + '1')
        
        # Add '0' only if the last character is '1' or if it's the start
        if not current or current[-1] == '1':
            backtrack(current + '0')
    
    backtrack("")
    return result
← Back to All Questions