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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


Input: n = 1

Output: ["0","1"]

Explanation:

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

Constraints

  • 1 <= n <= 18

Solution

Method 1 – Backtracking with Last Character Tracking

Intuition

To generate all valid binary strings of length n with no adjacent zeros, we can use backtracking. At each step, we can always add ‘1’, but we can only add ‘0’ if the previous character is not ‘0’.

Approach

  1. Define a backtracking function that takes the current string and the last character.
  2. If the string length is n, add it to the answer list.
  3. At each step:
    • Always try to add ‘1’.
    • Add ‘0’ only if the last character is not ‘0’.
  4. Start with an empty string and build recursively.
  5. Return the list of valid strings.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<string> generateStrings(int n) {
        vector<string> ans;
        function<void(string, char)> dfs = [&](string s, char last) {
            if (s.size() == n) { ans.push_back(s); return; }
            dfs(s + '1', '1');
            if (last != '0') dfs(s + '0', '0');
        };
        dfs("", '1');
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

type Solution struct{}
func (Solution) generateStrings(n int) []string {
    var ans []string
    var dfs func(s string, last byte)
    dfs = func(s string, last byte) {
        if len(s) == n {
            ans = append(ans, s)
            return
        }
        dfs(s+"1", '1')
        if last != '0' {
            dfs(s+"0", '0')
        }
    }
    dfs("", '1')
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public List<String> generateStrings(int n) {
        List<String> ans = new ArrayList<>();
        dfs("", '1', n, ans);
        return ans;
    }
    private void dfs(String s, char last, int n, List<String> ans) {
        if (s.length() == n) { ans.add(s); return; }
        dfs(s + "1", '1', n, ans);
        if (last != '0') dfs(s + "0", '0', n, ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun generateStrings(n: Int): List<String> {
        val ans = mutableListOf<String>()
        fun dfs(s: String, last: Char) {
            if (s.length == n) { ans.add(s); return }
            dfs(s + "1", '1')
            if (last != '0') dfs(s + "0", '0')
        }
        dfs("", '1')
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def generateStrings(self, n: int) -> list[str]:
        ans: list[str] = []
        def dfs(s: str, last: str):
            if len(s) == n:
                ans.append(s)
                return
            dfs(s + '1', '1')
            if last != '0':
                dfs(s + '0', '0')
        dfs('', '1')
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn generate_strings(n: i32) -> Vec<String> {
        fn dfs(s: String, last: char, n: i32, ans: &mut Vec<String>) {
            if s.len() == n as usize {
                ans.push(s);
                return;
            }
            dfs(format!("{}1", s), '1', n, ans);
            if last != '0' {
                dfs(format!("{}0", s), '0', n, ans);
            }
        }
        let mut ans = vec![];
        dfs(String::new(), '1', n, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
  generateStrings(n: number): string[] {
    const ans: string[] = [];
    function dfs(s: string, last: string) {
      if (s.length === n) { ans.push(s); return; }
      dfs(s + '1', '1');
      if (last !== '0') dfs(s + '0', '0');
    }
    dfs('', '1');
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(2^n), as each position can be ‘1’ or ‘0’ (with constraints), so the number of valid strings is less than 2^n but still exponential.
  • 🧺 Space complexity: O(2^n), for storing all valid strings.