# 3211. Generate Binary Strings Without Adjacent Zeros

## Description

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

## Solutions

### Solution 1: 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)$.

• 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) {
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);
}
}
}
}

• 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;
}
};

• 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


• 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
}

• 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;
}