Skip to content

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> validStrings(int n) {
        vector<string> ans;
        string t;
        auto dfs = [&](this 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(i + 1);
                    t.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
}

Comments