
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:
- Start with a base case for n = 1: - Valid strings are "0" and "1".
- 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').
- 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.
- 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;
};