LeetCode 3211 - Generate Binary Strings Without Adjacent Zeros
The problem asks us to generate every binary string of length n such that no substring of length 2 contains two consecutive zeros. A binary string contains only the characters "0" and "1". A substring of length 2 means every adjacent pair of characters in the string.
Difficulty: 🟡 Medium
Topics: String, Backtracking, Bit Manipulation
Solution
Problem Understanding
The problem asks us to generate every binary string of length n such that no substring of length 2 contains two consecutive zeros.
A binary string contains only the characters "0" and "1". A substring of length 2 means every adjacent pair of characters in the string. The condition says that every such pair must contain at least one "1". Another way to say this is that the string must never contain "00".
For example, the string "1011" is valid because its adjacent pairs are:
"10""01""11"
Every pair contains at least one "1".
On the other hand, "1001" is invalid because it contains the pair "00".
The input is a single integer n, representing the required length of the binary strings. The output should be a list containing all valid binary strings of that exact length. The order does not matter.
The constraint 1 <= n <= 18 is important. A binary string of length n has 2^n total possibilities. When n = 18, that becomes 262,144 possible strings. This is small enough that generating all valid answers with backtracking is feasible, but we still want to avoid unnecessary work.
Several edge cases are important:
- When
n = 1, both"0"and"1"are valid because there are no adjacent pairs to violate the condition. - Strings beginning with
"0"are allowed, as long as they do not contain consecutive zeros. - A naive implementation might accidentally generate invalid strings first and filter them later, which wastes work.
- Since the answer size itself can be exponential, the algorithm must efficiently prune invalid branches early.
Approaches
Brute Force Approach
The most straightforward approach is to generate every binary string of length n and then check whether each string contains "00".
We can think of every position independently choosing between "0" and "1". This creates 2^n total strings. For each generated string, we scan through it and verify that no adjacent pair equals "00".
This approach is correct because it examines every possible binary string and keeps exactly the valid ones.
However, it performs unnecessary work because it generates many invalid strings that could have been avoided during construction. For example, once we already build a partial string ending in "0", adding another "0" immediately creates an invalid string. Continuing beyond that point is wasteful.
Optimal Approach
The key observation is that the only invalid situation occurs when we place "0" immediately after another "0".
This means we can construct the strings incrementally using backtracking while enforcing the rule during generation itself. At each position:
- We can always place
"1". - We can place
"0"only if the previous character is not"0".
By pruning invalid branches early, we never build strings that contain "00".
This approach is more efficient because every recursive path always remains valid.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n × 2^n) | O(n) | Generates all binary strings, then validates each |
| Optimal | O(n × F(n)) | O(n) | Backtracking generates only valid strings |
Here, F(n) represents the number of valid strings, which follows a Fibonacci-like growth pattern.
Algorithm Walkthrough
- Initialize an empty result list that will store all valid binary strings.
- Use a backtracking function that keeps track of the current partially constructed string.
- If the current string length becomes
n, the string is complete and valid. Add it to the result list. - Always try adding
"1"first because placing"1"can never violate the rule. - To decide whether
"0"can be added, check the previous character:
- If the current string is empty,
"0"is allowed. - If the last character is
"1","0"is allowed. - If the last character is
"0", another"0"is forbidden.
- Recursively continue building the string after each valid choice.
- Backtracking automatically explores every valid possibility while pruning invalid branches immediately.
Why it works
The algorithm maintains the invariant that the current partial string never contains "00".
At every recursive step, we only append characters that preserve validity. Since invalid prefixes are never created, every completed string is guaranteed to be valid. Conversely, every valid string can be constructed through these choices, so no valid solution is missed.
Python Solution
from typing import List
class Solution:
def validStrings(self, n: int) -> List[str]:
result = []
def backtrack(current: str) -> None:
if len(current) == n:
result.append(current)
return
# Always allowed to place '1'
backtrack(current + "1")
# Place '0' only if previous character is not '0'
if not current or current[-1] != "0":
backtrack(current + "0")
backtrack("")
return result
The implementation closely follows the backtracking algorithm described earlier.
The result list stores all valid binary strings. The nested backtrack function constructs strings incrementally.
The base case checks whether the current string length equals n. If so, the string is complete and is added to the answer list.
The recursive logic has two branches. The first always appends "1" because it can never create consecutive zeros.
The second branch appends "0" only when the current string is empty or its last character is not "0". This guarantees that "00" is never introduced.
Because strings are immutable in Python, using current + "1" and current + "0" naturally creates new recursive states without manual cleanup.
Go Solution
func validStrings(n int) []string {
result := []string{}
var backtrack func(string)
backtrack = func(current string) {
if len(current) == n {
result = append(result, current)
return
}
// Always allowed to place '1'
backtrack(current + "1")
// Place '0' only if previous character is not '0'
if len(current) == 0 || current[len(current)-1] != '0' {
backtrack(current + "0")
}
}
backtrack("")
return result
}
The Go implementation follows the same recursive structure as the Python version.
One small difference is that Go uses byte indexing for string access. The expression current[len(current)-1] returns a byte, so we compare it against the character literal '0'.
The result slice starts empty and grows dynamically through append.
Go strings are immutable just like Python strings, so concatenation safely creates new recursive states.
Worked Examples
Example 1
Input:
n = 3
We start with an empty string.
| Current String | Action | Next String |
|---|---|---|
"" |
add "1" |
"1" |
"1" |
add "1" |
"11" |
"11" |
add "1" |
"111" |
"111" |
length = 3 | store |
"11" |
add "0" |
"110" |
"110" |
length = 3 | store |
"1" |
add "0" |
"10" |
"10" |
add "1" |
"101" |
"101" |
length = 3 | store |
"10" |
cannot add "0" |
stop branch |
"" |
add "0" |
"0" |
"0" |
add "1" |
"01" |
"01" |
add "1" |
"011" |
"011" |
length = 3 | store |
"01" |
add "0" |
"010" |
"010" |
length = 3 | store |
"0" |
cannot add "0" |
stop branch |
Final result:
["111", "110", "101", "011", "010"]
Any order is accepted.
Example 2
Input:
n = 1
| Current String | Action | Next String |
|---|---|---|
"" |
add "1" |
"1" |
"1" |
length = 1 | store |
"" |
add "0" |
"0" |
"0" |
length = 1 | store |
Final result:
["1", "0"]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n × F(n)) | We generate every valid string, each requiring O(n) construction cost |
| Space | O(n) | Recursive call stack depth is at most n |
The total number of valid strings follows a Fibonacci-like recurrence because each position depends on whether the previous character was "0" or "1".
The recursion depth never exceeds n, so auxiliary space remains linear. The output list itself is not counted in auxiliary space complexity.
Test Cases
from typing import List
class Solution:
def validStrings(self, n: int) -> List[str]:
result = []
def backtrack(current: str) -> None:
if len(current) == n:
result.append(current)
return
backtrack(current + "1")
if not current or current[-1] != "0":
backtrack(current + "0")
backtrack("")
return result
sol = Solution()
# Example case
assert sorted(sol.validStrings(3)) == sorted(
["010", "011", "101", "110", "111"]
), "Example 1"
# Smallest input
assert sorted(sol.validStrings(1)) == sorted(
["0", "1"]
), "n = 1 edge case"
# Length 2 valid strings
assert sorted(sol.validStrings(2)) == sorted(
["01", "10", "11"]
), "No consecutive zeros"
# Ensure '00' is excluded
assert "00" not in sol.validStrings(2), "Invalid consecutive zeros"
# Length 4 correctness
assert sorted(sol.validStrings(4)) == sorted(
[
"0101",
"0110",
"0111",
"1010",
"1011",
"1101",
"1110",
"1111",
]
), "General recursive generation"
# All outputs should have correct length
for s in sol.validStrings(5):
assert len(s) == 5, "Correct output length"
# All outputs should avoid consecutive zeros
for s in sol.validStrings(6):
assert "00" not in s, "Validity constraint"
# Stress test near upper limit
result = sol.validStrings(18)
for s in result:
assert len(s) == 18, "Large input handling"
assert "00" not in s, "Large input validity"
| Test | Why |
|---|---|
n = 3 |
Verifies the main example |
n = 1 |
Tests smallest valid input |
n = 2 |
Confirms basic generation logic |
Excluding "00" |
Ensures invalid strings are pruned |
n = 4 |
Tests deeper recursion |
| Length validation | Confirms all outputs have correct size |
| Consecutive zero validation | Ensures correctness invariant |
n = 18 |
Stress test near constraint limit |
Edge Cases
Edge Case 1: n = 1
This is the smallest possible input. Since there are no adjacent character pairs in a single-character string, both "0" and "1" are valid.
A buggy implementation might incorrectly forbid "0" entirely because it focuses too heavily on avoiding zeros. The recursive implementation handles this naturally because the empty string allows either character to be placed first.
Edge Case 2: Strings Starting With "0"
Some implementations mistakenly assume binary strings should start with "1" to avoid future problems. However, strings like "010" are perfectly valid because the zeros are not adjacent.
The algorithm correctly permits "0" at the beginning because the condition checks only whether the previous character was "0". An empty string has no previous character, so "0" is allowed.
Edge Case 3: Preventing Consecutive Zeros
The core challenge is ensuring "00" never appears.
A naive generator might create invalid strings and filter them afterward, which wastes computation. The backtracking approach prevents invalid states from ever being created by checking the last character before appending "0".
This pruning guarantees correctness while also improving efficiency.