Generate Binary Strings Without Adjacent Zeros - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Generate all binary strings of length n such that no two 0s appear next to each other. Every valid string must avoid the pattern "00". The output should contain all possible strings that satisfy this constraint.
Approach 1: Backtracking (O(2^n) time, O(n) space)
Backtracking builds the string one character at a time while enforcing the constraint early. At each position you try to append '1' or '0'. The only restriction: you cannot place '0' if the previous character was also '0'. This pruning prevents invalid branches like "00" from ever forming. The recursion continues until the string length reaches n, at which point the candidate is added to the result list. The algorithm explores at most two branches per step, but many are pruned, so the number of generated strings follows a Fibonacci-like pattern rather than the full 2^n. The recursion stack stores at most n characters, so auxiliary space is O(n). This approach is a classic application of backtracking combined with simple string construction.
Approach 2: Dynamic Programming Construction (O(n * F(n)) time, O(F(n)) space)
Dynamic programming can generate valid strings iteratively using the observation that a valid string depends on its last character. Maintain two groups for each length: strings ending with '1' and strings ending with '0'. If a string ends with '1', you may append either '0' or '1'. If it ends with '0', you may only append '1'. Starting from length 1 (["0", "1"]), repeatedly build the next length by applying these transitions. The number of valid strings follows Fibonacci growth, so generation time is proportional to the total output size F(n). This approach removes recursion and makes the state transition explicit, which can be easier to reason about in iterative implementations or when applying bit manipulation style construction.
Recommended for interviews: The backtracking solution is what most interviewers expect. It demonstrates that you can generate combinations while pruning invalid states early. A brute-force idea that generates all 2^n strings and filters "00" shows baseline understanding, but backtracking proves you can enforce constraints during generation and avoid unnecessary work.
Approach 1: Backtracking Approach
This method uses a backtracking strategy to generate all valid binary strings of length n. We start with an empty string and add '1' or '0' at each step, ensuring no consecutive '0's appear. If the previous character is '1', we can safely add both '1' and '0'. However, if the last character is '0', we can only add '1' to avoid invalid strings. This ensures all generated strings are valid.
This C code uses a recursive function generateStrings to build binary strings with backtracking, ensuring no substring of "00". It prints every valid string when the desired length n is reached, utilizing the base case when pos == n.
Complexity
Time Complexity: O(2^n), Space Complexity: O(n) for the recursion stack and temporary result storage.
Approach 2: Dynamic Programming Approach
This technique counts the number of valid binary strings without generating them. Define dp[i][0] as the number of valid strings of length i ending with '0' and dp[i][1] ending with '1'. Use these relationships:
dp[i][0] = dp[i-1][1], since a string ending in'0'must be preceded by a'1'.dp[i][1] = dp[i-1][0] + dp[i-1][1], as we can add'1'after any valid string.dp[1][0] = 1for'0',dp[1][1] = 1for'1'.
C code sets up a dynamic programming array, dp, to store numbers of valid strings, ensuring memory efficiency by only needing indices up to n.
Complexity
Time Complexity: O(n), Space Complexity: O(n) due to dp array.
Approach 3: DFS
We can enumerate each position i of a binary string of length n, and for each position i, we can enumerate the possible value j it can take. If j is 0, then we need to check if its previous position is 1. If it is 1, we can continue to recurse further; otherwise, it is invalid. If j is 1, then we directly recurse further.
The time complexity is O(n times 2^n), where n is the length of the string. Ignoring the space consumption of the answer array, the space complexity is O(n).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^n), Space Complexity: O(n) for the recursion stack and temporary result storage. |
| Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(n) due to |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^n) worst case (≈ Fibonacci outputs) | O(n) | Best for interviews and direct generation of valid strings with pruning |
| Dynamic Programming Construction | O(n * F(n)) | O(F(n)) | When you want an iterative solution without recursion |
Video Solution
3211 Generate Binary Strings Without Adjacent Zeros || Recursion and Simulation 🔥 • Ayush Rao • 3,339 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Generate Binary Strings Without Adjacent Zeros easy or hard?
Generate Binary Strings Without Adjacent Zeros Python/Java solution
How to solve Generate Binary Strings Without Adjacent Zeros in O(n)?
What is the best approach for Generate Binary Strings Without Adjacent Zeros?
Is Generate Binary Strings Without Adjacent Zeros asked at Google/Amazon/Meta?
What data structure is used in Generate Binary Strings Without Adjacent Zeros?
What is the time complexity of Generate Binary Strings Without Adjacent Zeros?
Ready to solve this problem?
Practice Generate Binary Strings Without Adjacent Zeros with our built-in code editor and test cases.
Practice on FleetCode