Generate Binary Strings Without Adjacent Zeros solution and explanation
Google
9 more videos on this problem
3211 Generate Binary Strings Without Adjacent Zeros || Recursion and Simulation 🔥Ayush Rao · 8:30 · 3K views
3211. Generate Binary Strings Without Adjacent Zeros | LeetCode 3211 | LeetCode Weekly Contest 405Amit Dhyani · 11:26 · 2K views
3211. Generate Binary Strings Without Adjacent Zeros | RecursionTech Courses · 5:03 · 819 views
Leetcode 3211: Generate Binary Strings Without Adjacent ZerosAlgorithms Casts · 6:42 · 702 views
3211. Generate Binary Strings Without Adjacent Zeros (Leetcode Medium)Programming Live with Larry · 6:13 · 512 views
Leetcode 3211. Generate Binary Strings Without Adjacent Zeros | Recursion Playlist using Java | DSADhananjay Sharma Officials · 19:26 · 436 views
Generate Binary Strings Without Adjacent Zeros | Leetcode 3211 | Backtracking, String | srkcodesSrk Codes · 12:43 · 370 views
LeetCode 3211 – Generate Binary Strings Without Adjacent ZerosWeb Coder Abhishek · 3:11 · 274 views
3211. Generate Binary Strings Without Adjacent Zeros | Recursion | String | BacktrackingLeet's Code · 6:44 · 204 views
“LeetCode 3211 – Generate Binary Strings Without Adjacent Zeros | Visual Backtracking l Codes Srish"Shrishty Gupta · 10:35 · 192 views
The 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
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.
def generate_strings(result, n, pos):
if pos == n:
print(result)
return
generate_strings(result + '1', n, pos + 1)
if pos == 0 or result[-1] != '0':
generate_strings(result + '0', n, pos + 1)
n = 3
generate_strings('', n, 0)public class Main {
public static void generateStrings(StringBuilder result, int n, int pos) {
if (pos == n) {
System.out.println(result);
return;
}
result.setCharAt(pos, '1');
generateStrings(result, n, pos + 1);
if (pos == 0 || result.charAt(pos - 1) != '0') {
result.setCharAt(pos, '0');
generateStrings(result, n, pos + 1);
}
}
public static void main(String[] args) {
int n = 3;
StringBuilder result = new StringBuilder(" ".repeat(n));
generateStrings(result, n, 0);
}
}#include <iostream>
#include <string>
using namespace std;
void generateStrings(string &result, int n, int pos) {
if (pos == n) {
cout << result << endl;
return;
}
result[pos] = '1';
generateStrings(result, n, pos + 1);
if (pos == 0 || result[pos - 1] != '0') {
result[pos] = '0';
generateStrings(result, n, pos + 1);
}
}
int main() {
int n = 3;
string result(n, ' ');
generateStrings(result, n, 0);
return 0;
}function generateStrings(result, n, pos) {
if (pos === n) {
console.log(result);
return;
}
generateStrings(result + '1', n, pos + 1);
if (pos === 0 || result[pos - 1] !== '0') {
generateStrings(result + '0', n, pos + 1);
}
}
let n = 3;
generateStrings('', n, 0);#include <stdio.h>
#include <string.h>
void generateStrings(char *result, int n, char *current, int pos) {
if (pos == n) {
result[pos] = '\0';
printf("%s\n", result);
return;
}
result[pos] = '1';
generateStrings(result, n, current, pos + 1);
if (pos == 0 || result[pos - 1] != '0') {
result[pos] = '0';
generateStrings(result, n, current, pos + 1);
}
}
int main() {
int n = 3;
char result[19]; // n <= 18
generateStrings(result, n, "", 0);
return 0;
}using System;
class Program {
static void GenerateStrings(string result, int n, int pos) {
if (pos == n) {
Console.WriteLine(result);
return;
}
GenerateStrings(result + '1', n, pos + 1);
if (pos == 0 || result[pos - 1] != '0') {
GenerateStrings(result + '0', n, pos + 1);
}
}
static void Main() {
int n = 3;
GenerateStrings("", n, 0);
}
}Python's dynamic string manipulation via + operator simplifies recursion without needing a preallocated space. The function prints valid binary strings respecting the no-consecutive-zeros rule.
Time Complexity: O(2^n), Space Complexity: O(n) for recursion depth.
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'.
def count_valid_strings(n):
dp = [[0, 0] for _ in range(n + 1)]
dp[1][0] = 1
dp[1][1] = 1
for i in range(2, n + 1):
dp[i][0] = dp[i - 1][1]
dp[i][1] = dp[i - 1][0] + dp[i - 1][1]
print(dp[n][0] + dp[n][1])
n = 3
count_valid_strings(n)public class Main {
public static void countValidStrings(int n) {
int[][] dp = new int[n + 1][2];
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
}
System.out.println(dp[n][0] + dp[n][1]);
}
public static void main(String[] args) {
int n = 3;
countValidStrings(n);
}
}#include <iostream>
#include <vector>
using namespace std;
void countValidStrings(int n) {
vector<vector<int>> dp(n + 1, vector<int>(2));
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
}
cout << (dp[n][0] + dp[n][1]) << endl;
}
int main() {
int n = 3;
countValidStrings(n);
return 0;
}function countValidStrings(n) {
let dp = Array.from({length: n + 1}, () => Array(2).fill(0));
dp[1][0] = 1;
dp[1][1] = 1;
for (let i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
}
console.log(dp[n][0] + dp[n][1]);
}
let n = 3;
countValidStrings(n);#include <stdio.h>
void countValidStrings(int n) {
int dp[n + 1][2];
dp[1][0] = 1;
dp[1][1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
}
printf("%d\n", dp[n][0] + dp[n][1]);
}
int main() {
int n = 3;
countValidStrings(n);
return 0;
}using System;
class Program {
static void CountValidStrings(int n) {
int[,] dp = new int[n + 1, 2];
dp[1, 0] = 1;
dp[1, 1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i, 0] = dp[i - 1, 1];
dp[i, 1] = dp[i - 1, 0] + dp[i - 1, 1];
}
Console.WriteLine(dp[n, 0] + dp[n, 1]);
}
static void Main() {
int n = 3;
CountValidStrings(n);
}
}Python implementation leverages a list of lists to model the dp table, efficiently counting all valid sequences of length n.
Time Complexity: O(n), Space Complexity: O(n) for 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).
function validStrings(n: number): string[] {
const ans: string[] = [];
const t: string[] = [];
const dfs = (i: number) => {
if (i >= n) {
ans.push(t.join(''));
return;
}
for (let j = 0; j < 2; ++j) {
if ((j == 0 && (i == 0 || t[i - 1] == '1')) || j == 1) {
t.push(j.toString());
dfs(i + 1);
t.pop();
}
}
};
dfs(0);
return ans;
}func validStrings(n int) (ans []string) {
t := []byte{}
var dfs func(int)
dfs = func(i int) {
if i >= n {
ans = append(ans, string(t))
return
}
for j := 0; j < 2; j++ {
if (j == 0 && (i == 0 || t[i-1] == '1')) || j == 1 {
t = append(t, byte('0'+j))
dfs(i + 1)
t = t[:len(t)-1]
}
}
}
dfs(0)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^n), Space Complexity: O(n) for recursion depth. |
| Dynamic Programming Approach | Time Complexity: O(n), Space Complexity: O(n) for dp array. |
| DFS | – |
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 |
Frequently asked questions
Is Generate Binary Strings Without Adjacent Zeros easy or hard?
The problem is typically classified as Medium. The constraint itself is simple, but recognizing that you should prune invalid branches using backtracking is the key insight. Once that idea is clear, the implementation is straightforward.
Generate Binary Strings Without Adjacent Zeros Python/Java solution
In Python or Java, implement a backtracking function that appends '1' always and appends '0' only if the previous character is not '0'. When the constructed string length reaches n, add it to the result list. This approach works the same across C++, JavaScript, C#, and Python.
How to solve Generate Binary Strings Without Adjacent Zeros in O(n)?
Generating all valid strings cannot be done in O(n) time because the output itself grows exponentially. However, counting the number of valid strings can be solved with dynamic programming in O(n) time using the recurrence similar to Fibonacci: dp[i] = dp[i-1] + dp[i-2].
What is the best approach for Generate Binary Strings Without Adjacent Zeros?
Backtracking is the most common and expected approach. Build the string one character at a time and only place '0' if the previous character is not '0'. This pruning guarantees that invalid "00" patterns never appear. The time complexity is O(2^n) in the worst case with O(n) recursion stack space.
Is Generate Binary Strings Without Adjacent Zeros asked at Google/Amazon/Meta?
Variants of this constraint-generation problem appear in interviews at companies like Google, Amazon, and Meta. The pattern tests understanding of backtracking, recursion, and pruning invalid states early. It is also related to Fibonacci-style DP counting problems.
What data structure is used in Generate Binary Strings Without Adjacent Zeros?
Most implementations use recursion with a mutable string or character array while building candidates. A list or vector stores the final results. Some iterative solutions maintain two lists representing strings ending in '0' and '1'.
What is the time complexity of Generate Binary Strings Without Adjacent Zeros?
The generation cost is proportional to the number of valid strings. In the worst case it is bounded by O(2^n), but the actual count follows Fibonacci growth because strings with "00" are pruned. The recursion stack or temporary string requires O(n) auxiliary space.