3211. Generate Binary Strings Without Adjacent Zeros LeetCode Solution

In this guide, you will get 3211. Generate Binary Strings Without Adjacent Zeros LeetCode Solution with the best time and space complexity. The solution to Generate Binary Strings Without Adjacent Zeros problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Generate Binary Strings Without Adjacent Zeros solution in C++
Generate Binary Strings Without Adjacent Zeros solution in Java
Generate Binary Strings Without Adjacent Zeros solution in Python
Additional Resources

3211. Generate Binary Strings Without Adjacent Zeros LeetCode Solution image

Problem Statement of Generate Binary Strings Without Adjacent Zeros

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

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(n \cdot 2^n)

3211. Generate Binary Strings Without Adjacent Zeros LeetCode Solution in C++

class Solution {
 public:
  vector<string> validStrings(int n) {
    vector<string> ans;
    dfs(n, "", ans);
    return ans;
  }

 private:
  void dfs(int n, string&& s, vector<string>& ans) {
    if (n == 0) {
      ans.push_back(s);
      return;
    }
    if (s.empty() || s.back() == '1') {
      s.push_back('0');
      dfs(n - 1, std::move(s), ans);
      s.pop_back();
    }
    s.push_back('1');
    dfs(n - 1, std::move(s), ans);
    s.pop_back();
  }
};
/* code provided by PROGIEZ */

3211. Generate Binary Strings Without Adjacent Zeros LeetCode Solution in Java

class Solution {
  public List<String> validStrings(int n) {
    List<String> ans = new ArrayList<>();
    dfs(n, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(int n, StringBuilder s, List<String> ans) {
    if (n == 0) {
      ans.add(s.toString());
      return;
    }
    if (s.isEmpty() || s.charAt(s.length() - 1) == '1') {
      s.append('0');
      dfs(n - 1, s, ans);
      s.deleteCharAt(s.length() - 1);
    }
    s.append('1');
    dfs(n - 1, s, ans);
    s.deleteCharAt(s.length() - 1);
  }
}
// code provided by PROGIEZ

3211. Generate Binary Strings Without Adjacent Zeros LeetCode Solution in Python

class Solution:
  def validStrings(self, n: int) -> list[str]:
    ans = []

    def dfs(n: int, s: list[str]) -> None:
      if n == 0:
        ans.append(''.join(s))
        return
      if not s or s[-1] == '1':
        s.append('0')
        dfs(n - 1, s)
        s.pop()
      s.append('1')
      dfs(n - 1, s)
      s.pop()

    dfs(n, [])
    return ans
 # code by PROGIEZ