3211. Generate Binary Strings Without Adjacent Zeros

Intuition

The problem requires generating binary strings of length n such that every substring of length 2 contains at least one '1'. This implies that consecutive zeros ('00') are not allowed, and every pair of characters in the string must include at least one '1'.

Approach

To generate valid binary strings:

1. Start with a base case for n = 1: - Valid strings are "0" and "1".
2. For n > 1, use a recursive approach: - Use backtracking or recursion to build the string incrementally. - Ensure that every time a new character ('0' or '1') is added, it maintains the validity condition (no consecutive '00').
3. Implement the solution using a depth-first search (DFS) approach: - Start with an empty string. - Append '0' or '1' to the string and recursively try adding the next character. - Backtrack if adding a character violates the validity condition.
4. Collect all valid strings generated by the above approach.

Complexity

The time complexity of the solution depends on the number of valid strings generated. For each string of length n, the worst-case scenario involves exploring all possible combinations without consecutive '00'. This results in an exponential time complexity in terms of the number of valid strings generated, which is \( O(2^n) \).

Space complexity mainly involves storing the valid strings generated, which is also \( O(2^n) \) in the worst case, considering all valid strings are stored in memory.

Code

C++

class Solution {
public:
    vector validStrings(int n) {
        vector res = {"0", "1"};
        vector tmp;
        
        for (int i = 1; i < n; ++i) {
            for (string x : res) {
                tmp.push_back(x + "1");
                if (x.back() == '1') tmp.push_back(x + "0");
            }
            res = tmp;
            tmp.clear();
        }
        
        return res;
    }
};

Python

class Solution:
    def validStrings(self, n: int) -> List[str]:
        res = ["0", "1"]
        tmp = []
        
        for i in range(1, n):
            for x in res:
                tmp.append(x + "1")
                if x.endswith("1"):
                    tmp.append(x + "0")
            
            res, tmp = tmp, res
            tmp.clear()
        
        return res

Java

class Solution {
    public List validStrings(int n) {
        List res = new ArrayList<>();
        res.add("0");
        res.add("1");
        List tmp = new ArrayList<>();
        
        for (int i = 1; i < n; ++i) {
            for (String x : res) {
                tmp.add(x + "1");
                if (x.endsWith("1")) {
                    tmp.add(x + "0");
                }
            }
            List temp = res;
            res = tmp;
            tmp = temp;
            tmp.clear();
        }
        
        return res;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {string[]}
 */
var validStrings = function (n) {
  var res = ["0", "1"];
  var tmp = [];
  for (var i = 1; i < n; ++i) {
    for (var x of res) {
      tmp.push(x + "1")
      if (x.endsWith("1")) tmp.push(x + "0");
    }
    [res, tmp] = [tmp, res];
    tmp.length = 0;
  }
  return res;
};