1770. Spaced Ones Strings
A row of n light switches is described by a string of '0' (off) and '1' (on). For safety reasons, two neighbouring switches may never both be on at the same time. Given the integer n, return every binary string of length n that has no two adjacent '1' characters.
The strings must be returned in ascending lexicographic order, where '0' comes before '1'. Build them with backtracking: at each position you may always place '0', and you may place '1' only at the very start or right after a '0'. Trying '0' before '1' produces the strings already in sorted order. There are at most 377 strings (for n = 12). The running time is proportional to the output size, O(n * F(n)) where F(n) is the number of valid strings, and the recursion uses O(n) extra space.
Example 1
- Input:
- n = 1
- Output:
- ["0","1"]
- Explanation:
Both single-character strings are valid.
Example 2
- Input:
- n = 3
- Output:
- ["000","001","010","100","101"]
- Explanation:
Of the 8 strings of length 3, the three containing "11" are removed, leaving 5.
Constraints
1 ≤ n ≤ 12 (at most 377 strings)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n * F(n))
- Space
- O(n)