Generate Binary Strings Without Adjacent Zeros

Generate Binary Strings Without Adjacent Zeros

What is this problem about?

The Generate Binary Strings Without Adjacent Zeros coding problem asks you to find all possible binary strings of length $n$ such that no two '0's are positioned next to each other. For example, if $n=3$, "101" and "110" are valid, but "100" is not. You need to return a list of all such valid strings in any order.

Why is this asked in interviews?

This problem is common at companies like Microsoft and Amazon to evaluate a candidate's mastery of Backtracking and state-space exploration. It evaluations whether you can correctly apply constraints during a recursive process to prune invalid branches early. This is a foundational task for many combinatorial and sequence-based problems where specific substrings or patterns are forbidden.

Algorithmic pattern used

This problem follows the Backtracking interview pattern.

1. Use a recursive function to build the string character by character.
2. At each step, you have two choices:
   • Option 1: Add '1'. This is always valid regardless of the previous character.
   • Option 2: Add '0'. This is only valid if the previous character was '1' (or if it's the first character of the string).
3. Base Case: When the current string length reaches $n$, add it to the result list.

Example explanation

$n = 2$

1. Start with empty string "".
2. Choice 1: Add '1'. Current: "1".
   • From "1", add '1' $o$ "11". (Base Case, Valid).
   • From "1", add '0' $o$ "10". (Base Case, Valid).
3. Choice 2: Add '0'. Current: "0".
   • From "0", can only add '1' (since adding '0' would violate the rule).
   • Add '1' $o$ "01". (Base Case, Valid). Result: ["11", "10", "01"].

Common mistakes candidates make

• Inefficient Filtering: Generating all $2^n$ binary strings and then checking for adjacent zeros. This is $O(2^n imes n)$, whereas backtracking with pruning is much faster ($O( ext{GoldenRatio}^n)$).
• Wrong state check: Failing to pass the "previous character" into the recursive call, making it difficult to verify the adjacency rule.
• Immutable String overhead: Repeatedly creating new string objects instead of using a character array or a string builder.

Interview preparation tip

Think of this as finding all paths in a state machine. State '0' can only transition to '1', while state '1' can transition to either '0' or '1'. Drawing a small decision tree helps you visualize the recursive calls.