Teaching Kids Programming – Fibonacci Numbers in (Generate Binary Strings Without Adjacent Zeros)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Example 1:
Input: n = 3
Output: [“010″,”011″,”101″,”110″,”111”]
Explanation:
The valid strings of length 3 are: “010”, “011”, “101”, “110”, and “111”.

Example 2:
Input: n = 1
Output: [“0″,”1”]
Explanation:
The valid strings of length 1 are: “0” and “1”.

Constraints:
1 <= n <= 18

Understanding the Fibonacci Pattern in Valid Binary Strings

Key Observation

The problem is equivalent to counting all binary strings of length n that do not contain consecutive zeros.

This is a classic problem whose solution count follows the Fibonacci sequence.

Why Fibonacci?

Let F(n) represent the number of valid strings of length n.

We observe the recurrence:

This is because:

• If a valid string ends with "1", we can add either "0" or "1".
• If it ends with "0", we can only add "1" to avoid "00".

This recurrence matches the Fibonacci pattern.

Examples of Valid String Counts

Python Code to Generate Valid Strings

1. Iterative (BFS-style)

def generate_valid_strings_iterative(n):
    if n == 0:
        return []
    result = ['0', '1']
    for i in range(1, n):
        new_result = []
        for s in result:
            if s[-1] == '0':
                new_result.append(s + '1')  # can't add '0' after '0'
            else:
                new_result.append(s + '0')
                new_result.append(s + '1')
        result = new_result
    return result

2. Recursive with Memoization

from functools import lru_cache

def generate_valid_strings_recursive(n):
    @lru_cache(maxsize=None)
    def dfs(pos, prev):
        if pos == n:
            return ['']
        res = []
        res += ['1' + tail for tail in dfs(pos + 1, '1')]
        if prev != '0':
            res += ['0' + tail for tail in dfs(pos + 1, '0')]
        return res

    return dfs(0, '')

Usage Example

n = 3
print("Iterative:", generate_valid_strings_iterative(n))
print("Recursive:", generate_valid_strings_recursive(n))

Why F(n) = F(n – 1) + F(n – 2)?

Core Rule

A binary string is valid if it contains no consecutive 0s.

Recursive Construction

We want to construct valid binary strings of length n by extending valid strings of smaller lengths.

Case 1: String ends with '1'

• Any valid string of length n - 1 can be safely extended by appending '1'.
• This is always safe because appending '1' never introduces a "00" pattern.
• This contributes F(n - 1) valid strings.

Case 2: String ends with '0'

• We can only append '0' if the previous character is '1' to avoid "00".
• This means we must append "10" to a valid string of length n - 2.
• This contributes F(n - 2) valid strings.

Recurrence Relation

F(n) = F(n - 1) + F(n - 2)

Example: n = 4

F(3) = 5 Valid Strings:

• 010
• 011
• 101
• 110
• 111

• Each of these can be extended with '1' → contributes to F(3)

F(2) = 3 Valid Strings:

• 01
• 10
• 11

• Each of these can be extended with "10" → contributes to F(2)

Total:

F(4) = F(3) + F(2) = 5 + 3 = 8

Conclusion

• Appending '1' is always allowed → F(n - 1)
• Appending '10' ensures no "00" → F(n - 2)
• This matches the Fibonacci recurrence.

Conclusion

This problem is a beautiful example of how combinatorics, dynamic programming, and recursion intersect. The Fibonacci sequence naturally emerges from the constraint “no two consecutive zeros”, making it both an elegant and instructive pattern in algorithm design.

You can apply the same technique to other problems involving restricted binary string patterns, especially in coding interviews or competitive programming.

Generate Binary Strings Without Adjacent Zeros

• Teaching Kids Programming - Fibonacci Numbers in Generate Binary Strings Without Adjacent Zeros
• Teaching Kids Programming - Another BFS to Generate Binary Strings Without Adjacent Zeros
• Teaching Kids Programming - Generate Binary Strings Without Adjacent Zeros (Breadth First Search Algorithm)
• Teaching Kids Programming - Generate Binary Strings Without Adjacent Zeros (Recursive Depth First Search Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —