# Generate Binary Strings Without Adjacent Zeros
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/generate-binary-strings-without-adjacent-zeros)
Canonical: https://scaleengineer.com/dsa/problems/generate-binary-strings-without-adjacent-zeros
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** String
---
## Problem
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"\]

**Explanation:**

The valid strings of length 3 are: `"010"`, `"011"`, `"101"`, `"110"`, and `"111"`.

**Example 2:**

**Input:** n = 1

**Output:** \["0","1"\]

**Explanation:**

The valid strings of length 1 are: `"0"` and `"1"`.

**Constraints:**

* `1 <= n <= 18`

# Approaches
## Brute Force: Generate All and Filter
This straightforward approach generates every possible binary string of length `n` and then filters them based on the given validity condition. A string is considered valid if it does not contain the substring "00". While simple to conceive, this method is inefficient because it processes many strings that will ultimately be discarded.
**Time:** O(n * 2^n). The outer loop runs `2^n` times. Inside the loop, building the string takes `O(n)` and checking `contains("00")` takes `O(n)`. Thus, the total time complexity is `O(n * 2^n)`. · **Space:** O(n * F_{n+2}). The space required to store the output list dominates. There are `F_{n+2}` (Fibonacci number) valid strings of length `n`, and each has length `n`. The auxiliary space used within the loop is `O(n)` for the `StringBuilder`.
**Pros:** Conceptually simple and easy to implement without recursion.
**Cons:** Highly inefficient as it generates and processes a large number of invalid strings, especially for larger `n`.; The time complexity grows exponentially with `n` at a faster rate (`2^n`) than the optimal solution.
### Explanation
The core of this method is to map the integers in the range `[0, 2^n - 1]` to all possible binary strings of length `n`. For example, if `n=3`, the integer `5` (binary `101`) maps to the string "101". We can implement this by iterating from `i = 0` to `(1 << n) - 1`. Inside the loop, we build a `StringBuilder` of length `n`. We iterate from `j = n-1` down to `0` to check the bits of `i` from most significant to least significant. The expression `(i & (1 << j)) != 0` checks if the `j`-th bit of `i` is set. If it is, we append '1'; otherwise, we append '0'. Once the `n`-character string is formed, we use a built-in `contains` method to check for the "00" substring. If it's not found, the string is added to our list of results.
```java
class Solution {
    public List<String> validStrings(int n) {
        List<String> result = new ArrayList<>();
        // Total number of binary strings of length n is 2^n
        int limit = 1 << n; 
        for (int i = 0; i < limit; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = n - 1; j >= 0; j--) {
                // Check if the j-th bit is 1 or 0
                if ((i & (1 << j)) != 0) {
                    sb.append('1');
                } else {
                    sb.append('0');
                }
            }
            String currentString = sb.toString();
            // Check for "00" substring
            if (!currentString.contains("00")) {
                result.add(currentString);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an empty list, `result`, to store the valid strings.
*   Iterate through all integers from `0` to `2^n - 1`. Each integer represents a unique binary string of length `n`.
*   For each integer, convert it to its `n`-bit binary string representation. This can be done by checking each bit of the integer.
*   Check if the generated binary string contains the forbidden substring "00".
*   If the string is valid (does not contain "00"), add it to the `result` list.
*   After checking all `2^n` possibilities, return the `result` list.

## Efficient Backtracking
A more optimized approach is to use backtracking to construct the valid strings directly. This method avoids generating invalid strings by making decisions at each step that maintain the validity constraint. We build the string character by character, and at each position, we only add a '0' or '1' if it doesn't violate the rule of having no adjacent zeros.
**Time:** O(n * F_{n+2}). The number of valid strings is given by the Fibonacci number `F_{n+2}`. The recursion tree has this many leaf nodes. Generating each string of length `n` involves a path of length `n` in the tree. The total work is proportional to the total number of nodes in the tree, which is on the order of `F_{n+2}`, and converting the `StringBuilder` to a `String` at each leaf node takes `O(n)`. · **Space:** O(n * F_{n+2}). The primary space cost is for storing the `result` list. The recursion depth is `n`, so the call stack and the `StringBuilder` use `O(n)` auxiliary space.
**Pros:** Highly efficient and optimal, as it only explores the search space of valid strings.; Scales well within the given constraints (`n <= 18`).
**Cons:** The logic is slightly more complex than the brute-force method due to recursion and backtracking.
### Explanation
This approach uses a recursive depth-first search to explore the space of valid binary strings. We define a helper function, `backtrack(current, n, result)`, which takes the current prefix `current` (as a `StringBuilder`), the target length `n`, and the list of `result` strings.

The recursion is initiated by making two separate calls for the starting characters: one for "0" and one for "1". This handles the strings of length 1 and seeds the recursion for longer strings.

Inside the `backtrack` function:
1.  **Base Case**: The recursion stops when `current.length()` equals `n`. At this point, we have constructed a complete, valid string, which is added to the `result` list.
2.  **Recursive Step**: The function checks the last character of the `current` string to decide the next valid moves:
    *   If the last character is '1', we have two choices for the next character: '0' or '1'. The function recursively calls itself for both cases. First, it appends '0', makes the recursive call, and then backtracks by removing the '0'. Then, it does the same for '1'.
    *   If the last character is '0', the only valid next character is '1' to avoid a "00" sequence. The function appends '1', makes the recursive call, and then backtracks.

Using a `StringBuilder` and deleting the last character for backtracking is crucial for efficiency, as it avoids creating numerous intermediate string objects.
```java
class Solution {
    public List<String> validStrings(int n) {
        List<String> result = new ArrayList<>();
        if (n <= 0) return result;
        // Start the recursion for strings beginning with "0" and "1"
        backtrack(new StringBuilder("0"), n, result);
        backtrack(new StringBuilder("1"), n, result);
        return result;
    }

    private void backtrack(StringBuilder current, int n, List<String> result) {
        // Base case: a valid string of length n is found
        if (current.length() == n) {
            result.add(current.toString());
            return;
        }

        char lastChar = current.charAt(current.length() - 1);

        // If the last character was '0', the next must be '1'
        if (lastChar == '0') {
            current.append('1');
            backtrack(current, n, result);
            current.deleteCharAt(current.length() - 1); // Backtrack
        } 
        // If the last character was '1', the next can be '0' or '1'
        else { // lastChar == '1'
            // Option 1: Append '0'
            current.append('0');
            backtrack(current, n, result);
            current.deleteCharAt(current.length() - 1); // Backtrack

            // Option 2: Append '1'
            current.append('1');
            backtrack(current, n, result);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
    }
}
```
### Algorithm
*   Define a recursive function, let's call it `backtrack`, that takes the current string being built (e.g., as a `StringBuilder`) as a parameter.
*   **Base Case**: If the length of the current string equals `n`, it's a complete valid string. Add it to the results list and return.
*   **Recursive Step**: Based on the last character of the current string:
    *   If the last character is '1', we can append either '0' or '1'. Make a recursive call for each possibility, backtracking after each call.
    *   If the last character is '0', we can only append '1'. Make a recursive call and backtrack.
*   The process is initiated by making separate calls for initial strings "0" and "1".

# Solutions
### Java

```java
class Solution { private List < String > ans = new ArrayList <>(); private StringBuilder t = new StringBuilder (); private int n ; public List < String > validStrings ( int n ) { this . n = n ; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i >= n ) { ans . add ( t . toString ()); return ; } for ( int j = 0 ; j < 2 ; ++ j ) { if (( j == 0 && ( i == 0 || t . charAt ( i - 1 ) == '1' )) || j == 1 ) { t . append ( j ); dfs ( i + 1 ); t . deleteCharAt ( t . length () - 1 ); } } } }
```

### CPP

```cpp
class Solution { public: vector < string > validStrings ( int n ) { vector < string > ans ; string t ; auto dfs = [ & ]( auto && dfs , int i ) { if ( i >= n ) { ans . emplace_back ( t ); return ; } for ( int j = 0 ; j < 2 ; ++ j ) { if (( j == 0 && ( i == 0 || t [ i - 1 ] == '1' )) || j == 1 ) { t . push_back ( '0' + j ); dfs ( dfs , i + 1 ); t . pop_back (); } } }; dfs ( dfs , 0 ); return ans ; } };
```

### Python

```python
class Solution : def validStrings ( self , n : int ) -> List [ str ]: def dfs ( i : int ): if i >= n : ans . append ( "" . join ( t )) return for j in range ( 2 ): if ( j == 0 and ( i == 0 or t [ i - 1 ] == "1" )) or j == 1 : t . append ( str ( j )) dfs ( i + 1 ) t . pop () ans = [] t = [] dfs ( 0 ) return ans
```