Binary Strings With No Adjacent Ones
Problem
Given a length n, return every binary string of that length in which no two 1s are next to each other. Return the strings in increasing order.
Examples
Input: n = 3
Output: ["000", "001", "010", "100", "101"]
Why: 011, 110 and 111 each put two 1s side by sideInput: n = 1
Output: ["0", "1"]Input: n = 0
Output: [""]
Why: edge case, the empty string is the one string of length zeroHints
0 / 3
Generating all 2 to the power n strings and filtering them wastes work on strings that broke the rule at their second character. Can you stop a bad string as soon as it goes wrong?
Build the string one character at a time. At each position the choices are 0 and 1, and 1 is only allowed when the previous character is not 1.
Write a recursive helper that appends 0, recurses and removes it, then appends 1 only when the string is empty or ends in 0, recurses and removes it. Trying 0 before 1 produces the strings in increasing order.
Solution
Each position is a level of the decision tree with two branches, 0 and 1, and the rule prunes the 1 branch whenever the previous character is already 1. A pruned branch is never explored, so every leaf the search reaches is a valid string and nothing is filtered afterwards. Trying 0 before 1 at every level visits the leaves in increasing order. The number of valid strings grows like the Fibonacci numbers, and each one costs O(n) to join, so time is O(n · F(n + 2)) and the recursion uses O(n) extra space beyond the output.
def no_adjacent_ones(n):
result, path = [], []
def build():
if len(path) == n:
result.append("".join(path))
return
path.append("0")
build()
path.pop()
if not path or path[-1] == "0": # prune: a 1 may not follow a 1
path.append("1")
build()
path.pop()
build()
return result
print(no_adjacent_ones(3)) # -> ['000', '001', '010', '100', '101']
print(no_adjacent_ones(1)) # -> ['0', '1']
print(no_adjacent_ones(0)) # -> ['']Stuck on the idea rather than the code? The Decision Tree covers it.