Problem Description

You are given a positive integer n and need to generate all valid binary strings of length n.

A binary string is considered valid if every substring of length 2 contains at least one "1". In other words, you cannot have two consecutive "0"s anywhere in the string.

For example:

• "101" is valid because all substrings of length 2 ("10" and "01") contain at least one "1"
• "100" is invalid because the substring "00" contains no "1"
• "111" is valid because all substrings of length 2 ("11" and "11") contain at least one "1"
• "1010" is valid because all substrings of length 2 ("10", "01", "10") contain at least one "1"

The solution uses a depth-first search (DFS) approach to build valid strings character by character. At each position i, it tries to place either "0" or "1". When placing a "0", it checks if the previous character is "1" (to avoid consecutive zeros). When placing a "1", it can always proceed since "1" followed by any character will form a valid substring. The algorithm recursively builds all possible valid strings and collects them in the result list.

The function returns all valid binary strings of length n in any order.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves generating binary strings, not graph traversal with nodes and edges.

Need to solve for kth smallest/largest?

• No: We need to generate all valid strings, not find a specific kth element.

Involves Linked Lists?

• No: The problem is about generating strings, not manipulating linked list structures.

Does the problem have small constraints?

• Yes: The problem asks us to generate all valid binary strings of length n. Since we need to enumerate all possibilities and return them as a list, n is typically small (otherwise the output would be exponentially large). For a string of length n, there can be at most 2^n possible strings.

Brute force / Backtracking?

• Yes: We need to explore all possible valid binary strings by trying different choices at each position. This is a classic backtracking scenario where we:
  • Build the string character by character
  • At each position, try placing either '0' or '1'
  • Check validity constraints (no consecutive zeros)
  • Backtrack if invalid or continue building
  • Collect complete valid strings

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This matches the solution perfectly - we recursively build strings position by position, validate constraints (checking if we can place a '0' based on the previous character), and backtrack when needed to explore all valid possibilities.

Intuition

When we need to generate all valid binary strings with a specific constraint, we can think of building the string one character at a time. At each position, we have two choices: place a '0' or place a '1'.

The key constraint here is that we cannot have two consecutive '0's. This means whenever we want to place a '0' at position i, we need to ensure that the character at position i-1 is not '0' (it must be '1'). On the other hand, we can always place a '1' at any position without violating the constraint.

This naturally leads to a backtracking approach where we:

1. Start with an empty string and try to build it character by character
2. At each position, explore both possibilities ('0' and '1')
3. Before placing a '0', check if it's valid (either it's the first character, or the previous character is '1')
4. When we reach length n, we've found a valid string - add it to our result
5. Backtrack by removing the last character to explore other possibilities

The beauty of this approach is that we prune invalid paths early. If placing a '0' would create consecutive zeros, we don't explore that branch at all, making the algorithm efficient despite exploring all possibilities.

Think of it like navigating a decision tree where each level represents a position in the string, and each branch represents choosing either '0' or '1'. We traverse this tree depth-first, collecting all paths that lead to valid strings of length n.

Learn more about Backtracking patterns.

Solution Approach

The solution implements a depth-first search (DFS) with backtracking to generate all valid binary strings. Let's walk through the implementation:

Core Algorithm Structure:

The solution uses a recursive DFS function dfs(i) where i represents the current position we're building in the string. We maintain a temporary list t to build the current string candidate and an answer list ans to collect all valid strings.

Building Process:

1. Base Case: When i >= n, we've successfully built a string of length n. We join the characters in t to form a string and add it to ans.

2. Recursive Case: For each position i, we try both possible values (j = 0 and j = 1):

   • If j = 0: We can only place a '0' if either:
     • It's the first position (i == 0), OR
     • The previous character is '1' (t[i - 1] == "1")
   • If j = 1: We can always place a '1' without any checks

Backtracking Mechanism:

After exploring a choice (adding a character to t and recursing), we backtrack by removing the last character (t.pop()). This allows us to explore the alternative choice at the same position.

Implementation Details:

def dfs(i: int):
    if i >= n:
        ans.append("".join(t))  # Found a valid string
        return
  
    for j in range(2):  # Try both 0 and 1
        if (j == 0 and (i == 0 or t[i - 1] == "1")) or j == 1:
            t.append(str(j))  # Make choice
            dfs(i + 1)        # Explore further
            t.pop()           # Backtrack

The condition (j == 0 and (i == 0 or t[i - 1] == "1")) or j == 1 ensures we only place valid characters:

• Place '0' only if it's the first character or preceded by '1'
• Always allow placing '1'

Time and Space Complexity:

• Time: O(2^n) in the worst case, as we might generate up to 2^n valid strings
• Space: O(n) for the recursion stack and temporary string building

This approach efficiently generates all valid strings by pruning invalid branches early in the recursion tree.

Example Walkthrough

Let's walk through generating all valid binary strings for n = 3.

Initial Setup:

• n = 3
• t = [] (temporary string builder)
• ans = [] (result list)

DFS Traversal:

Starting at position i = 0:

Path 1: Start with '1'

• i = 0: Add '1' → t = ['1']
• i = 1: Previous is '1', can add '0' or '1'
  • Path 1.1: Add '0' → t = ['1', '0']
    • i = 2: Previous is '0', can only add '1'
      • Add '1' → t = ['1', '0', '1']
      • i = 3: Base case reached, add "101" to ans
      • Backtrack → t = ['1', '0']
    • Backtrack → t = ['1']
  • Path 1.2: Add '1' → t = ['1', '1']
    • i = 2: Previous is '1', can add '0' or '1'
      • Path 1.2.1: Add '0' → t = ['1', '1', '0']
        • i = 3: Base case reached, add "110" to ans
        • Backtrack → t = ['1', '1']
      • Path 1.2.2: Add '1' → t = ['1', '1', '1']
        • i = 3: Base case reached, add "111" to ans
        • Backtrack → t = ['1', '1']
    • Backtrack → t = ['1']
• Backtrack → t = []

Path 2: Start with '0'

• i = 0: Add '0' (allowed as first character) → t = ['0']
• i = 1: Previous is '0', can only add '1'
  • Add '1' → t = ['0', '1']
  • i = 2: Previous is '1', can add '0' or '1'
    • Path 2.1: Add '0' → t = ['0', '1', '0']
      • i = 3: Base case reached, add "010" to ans
      • Backtrack → t = ['0', '1']
    • Path 2.2: Add '1' → t = ['0', '1', '1']
      • i = 3: Base case reached, add "011" to ans
      • Backtrack → t = ['0', '1']
  • Backtrack → t = ['0']
• Backtrack → t = []

Final Result: ans = ["101", "110", "111", "010", "011"]

All 5 strings satisfy the constraint of having no consecutive zeros. Notice how the algorithm automatically avoided generating invalid strings like "100" or "001" by checking the previous character before placing a '0'.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 2^n)

The algorithm uses depth-first search to generate all valid binary strings of length n. At each position, we have at most 2 choices (0 or 1), but the choice of 0 is restricted when the previous character is 0. In the worst case, we generate approximately 2^n valid strings. For each valid string, we need O(n) time to join the characters and append to the result. Therefore, the total time complexity is O(n × 2^n).

Space Complexity: O(n)

The space complexity analysis excludes the space used for the answer array. The recursive call stack can go up to depth n, and the temporary list t stores at most n characters at any point. Both contribute O(n) space. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Validation Logic for Consecutive Zeros

Pitfall: A common mistake is incorrectly checking for consecutive zeros by either:

• Forgetting to handle the edge case when position == 0 (first character can be '0')
• Using wrong index access like current_string[position] instead of current_string[position - 1]
• Checking the wrong condition, such as allowing '0' when the previous character is also '0'

Incorrect Example:

# Wrong: This allows consecutive zeros
if digit == 0 and current_string[-1] == "0":  # Incorrect logic
    current_string.append("0")

# Wrong: Index out of bounds when position == 0
if digit == 0 and current_string[position - 1] == "1":  # Crashes when position == 0
    current_string.append("0")

Solution: Always check if it's the first position before accessing previous elements:

if digit == 0:
    if position == 0 or current_string[position - 1] == "1":
        current_string.append("0")
        backtrack(position + 1)
        current_string.pop()

2. Forgetting to Backtrack

Pitfall: Failing to remove the added character after recursion, which causes the current_string to grow incorrectly and produce wrong results.

Incorrect Example:

current_string.append(str(digit))
backtrack(position + 1)
# Missing: current_string.pop()

Solution: Always pair append with pop in backtracking:

current_string.append(str(digit))
backtrack(position + 1)
current_string.pop()  # Essential for backtracking

3. String Concatenation Instead of List Building

Pitfall: Using string concatenation in recursion, which creates new string objects at each step and significantly degrades performance.

Inefficient Example:

def backtrack(position: int, current: str) -> None:
    if position >= n:
        result.append(current)
        return
  
    # Inefficient: creates new string objects
    backtrack(position + 1, current + "0")  
    backtrack(position + 1, current + "1")

Solution: Use a list for building strings and join only when complete:

current_string = []  # Use list
current_string.append(str(digit))  # O(1) operation
# ... recursion ...
result.append("".join(current_string))  # Join only at the end

4. Off-by-One Errors in Base Case

Pitfall: Using incorrect comparison in the base case, such as position > n instead of position >= n, which either generates strings of wrong length or causes infinite recursion.

Incorrect Example:

if position == n - 1:  # Wrong: stops too early
    result.append("".join(current_string))
    return

Solution: Use the correct boundary check:

if position >= n:  # Correct: we've filled all n positions (0 to n-1)
    result.append("".join(current_string))
    return