Generate Binary Strings Without Adjacent Zeros

Generate Binary Strings Without Adjacent Zeros - Problem

You are given a positive integer n. A binary string x is valid if all substrings of x of length 2 contain at least one "1".

Return all valid strings with length n, in any order.

In other words, no two consecutive zeros ("00") are allowed in any valid binary string.

Input & Output

Example 1 — Basic Case

$ Input: n = 3

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

💡 Note: All valid 3-length binary strings without consecutive zeros. Note that "000", "001", and "100" are invalid because they contain "00".

Example 2 — Minimum Size

$ Input: n = 1

› Output: ["0","1"]

💡 Note: For length 1, both "0" and "1" are valid since there are no substrings of length 2 to check.

Example 3 — Small Case

$ Input: n = 2

› Output: ["01","10","11"]

💡 Note: For length 2, "00" is invalid (contains consecutive zeros), but "01", "10", and "11" are all valid.

Constraints

1 ≤ n ≤ 20

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=3, need all valid binary strings of length 3

Constraint

No substring '00' allowed - must have at least one '1' in every 2-char window

Output

All valid strings: '010', '011', '101', '110', '111'

Key Takeaway

🎯 Key Insight: After placing a '0', the next position must be '1' to avoid consecutive zeros

Asked in

G Google 25 a Amazon 18 M Microsoft 15 Apple 12

The key insight is recognizing that valid binary strings without consecutive zeros follow the Fibonacci sequence pattern. The optimal approach uses backtracking to generate only valid strings by enforcing the constraint that after placing '0', the next character must be '1'. Time: O(φⁿ), Space: O(φⁿ) where φ≈1.618 is the golden ratio.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Generation	O(n × 2ⁿ)	O(n × 2ⁿ)	Generate all possible binary strings and filter valid ones
Backtracking	O(φⁿ)	O(n × φⁿ)	Build valid strings character by character using recursive backtracking
Dynamic Programming with Fibonacci Pattern	O(φⁿ)	O(φⁿ)	Use DP to count valid strings and generate them efficiently

Brute Force Generation — Algorithm Steps

Generate all 2^n binary strings of length n
For each string, check if it contains '00' substring
Keep only strings without consecutive zeros

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all 2^n binary strings

Check Each

Validate each string for consecutive zeros

Filter Valid

Keep only strings without '00'

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

char** solution(int n, int* returnSize) {
    int maxStrings = (int)pow(2, n);
    char** result = (char**)malloc(maxStrings * sizeof(char*));
    *returnSize = 0;
    
    // Generate all possible binary strings of length n
    for (int i = 0; i < (1 << n); i++) {
        char* binaryStr = (char*)malloc((n + 1) * sizeof(char));
        // Convert number to binary string
        for (int j = n - 1; j >= 0; j--) {
            binaryStr[n - 1 - j] = ((i >> j) & 1) ? '1' : '0';
        }
        binaryStr[n] = '\0';
        
        // Check if string is valid (no consecutive zeros)
        int valid = 1;
        for (int j = 0; j < n - 1; j++) {
            if (binaryStr[j] == '0' && binaryStr[j+1] == '0') {
                valid = 0;
                break;
            }
        }
        
        if (valid) {
            result[*returnSize] = binaryStr;
            (*returnSize)++;
        } else {
            free(binaryStr);
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int returnSize;
    char** result = solution(n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

Generate 2^n strings, check each string in O(n) time

✓ Linear Growth

Space Complexity

O(n × 2ⁿ)

Store all generated strings and result array

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler