Dare2Solve
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'.
To generate valid binary strings:
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.
class Solution {
public:
vector<string> validStrings(int n) {
vector<string> res = {"0", "1"};
vector<string> 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;
}
};
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
class Solution {
public List<String> validStrings(int n) {
List<String> res = new ArrayList<>();
res.add("0");
res.add("1");
List<String> 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<String> temp = res;
res = tmp;
tmp = temp;
tmp.clear();
}
return res;
}
}
/**
* @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;
};