#3211

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Generate Binary Strings Without Adjacent Zeros

Generate all binary strings of length n without adjacent zeros using backtracking search with pruning for efficient enumeration.

string backtracking bit manipulation

Problem Statement

Given a positive integer n, generate all binary strings of length n where no two zeros appear consecutively. Each valid string must have every substring of length 2 contain at least one 1.

Return a list of all valid binary strings in any order. For example, for n = 3, valid strings include "010", "011", "101", "110", and "111".

Examples

Example 1

Input: n = 3

Output: ["010","011","101","110","111"]

The valid strings of length 3 are: "010" , "011" , "101" , "110" , and "111" .

Example 2

Input: n = 1

Output: ["0","1"]

The valid strings of length 1 are: "0" and "1" .

Constraints

1 <= n <= 18

Solution Approach

Recursive Backtracking

Start with an empty string and recursively append 0 or 1. Only append 0 if the previous character is 1 to prevent adjacent zeros. Collect strings when the desired length is reached.

Pruning Invalid Prefixes

At each recursion step, check the last character before appending 0. If two zeros would be consecutive, skip that branch. This reduces unnecessary exploration and speeds up generation.

Bit Manipulation Optimization

Represent strings as integers and use bitwise operations to test the last bit before adding a new one. This can reduce memory overhead and improve performance for larger n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The number of valid strings follows a Fibonacci-like growth since each string ending with 1 allows both 0 and 1 next, and strings ending with 0 allow only 1. Time and space complexity are exponential in n but pruned using backtracking.

What Interviewers Usually Probe

Expect an understanding of recursive generation and pruning strategies for string enumeration.
Check if you consider the constraint preventing consecutive zeros before recursion.
Notice if the candidate optimizes memory or speed using bit-level representation.

Common Pitfalls or Variants

Common pitfalls

Appending 0 without checking the previous character leads to invalid strings.
Trying to generate all 2^n strings before filtering is inefficient and fails for larger n.
Forgetting to collect strings only after reaching length n can create duplicates or incomplete results.

Follow-up variants

Generate ternary strings avoiding two consecutive zeros or twos.
Count the number of valid strings instead of listing them, which reduces memory use.
Modify the pattern to avoid k consecutive zeros instead of just two.

FAQ

What is the simplest method to generate strings without adjacent zeros?

Use backtracking to append 0 or 1 recursively, only allowing 0 if the previous character is 1.

Can bit manipulation speed up generating binary strings?

Yes, representing strings as integers lets you use bit operations to check previous bits efficiently.

How does GhostInterview help with this backtracking pattern?

It visualizes recursive calls and pruning, ensuring no branch creates consecutive zeros and all valid strings are collected.

What is the maximum n feasible for full string generation?

Due to exponential growth, practical generation works efficiently up to n = 18 with pruning.

Are there common mistakes when solving this problem?

Yes, including appending 0 after 0 without checks, generating all 2^n strings first, or collecting incomplete strings.

terminal

Solution

Solution 1: DFS

We can enumerate each position $i$ of a binary string of length $n$, and for each position $i$, we can enumerate the possible value $j$ it can take. If $j$ is $0$, then we need to check if its previous position is $1$. If it is $1$, we can continue to recurse further; otherwise, it is invalid. If $j$ is $1$, then we directly recurse further.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def validStrings(self, n: int) -> List[str]:
        def dfs(i: int):
            if i >= n:
                ans.append("".join(t))
                return
            for j in range(2):
                if (j == 0 and (i == 0 or t[i - 1] == "1")) or j == 1:
                    t.append(str(j))
                    dfs(i + 1)
                    t.pop()

        ans = []
        t = []
        dfs(0)
        return ans

Continue Practicing

#3348 smallest divisible digit product ii #3376 minimum time to break locks i #3003 maximize the number of partitions after operations