Teaching Kids Programming – Another BFS to 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

Generate Binary Strings Without Adjacent Zeros (Another Breadth First Search Algorithm)

Binary strings—sequences composed solely of ‘0’s and ‘1’s—are fundamental in computer science and digital systems. A common problem is generating all possible binary strings of length n that do not contain consecutive zeros. This article presents a Python solution to this problem using an iterative approach (in the same manner of Breadth First Search Algorithm).

The solution builds the binary strings iteratively, starting from length 1 and extending up to length n. At each step, new strings are formed by appending ‘0’ or ‘1’ to the existing strings, ensuring that no string ends with ’00’.

Here’s the Python code implementing the described approach:

from typing import List

class Solution:
    def validStrings(self, n: int) -> List[str]:
        if n == 0:
            return []
        if n == 1:
            return ["0", "1"]
        
        ans = ["0", "1"]
        for i in range(1, n):
            cur = []
            for x in ans:
                if x[-1] == '1':
                    cur.append(x + "0")
                cur.append(x + "1")
            ans = cur
        return ans

Explanation:
Base Cases:

• If n == 0, return an empty list since there are no binary strings of length 0.
• If n == 1, return [“0”, “1”] as the only binary strings of length 1.

Iterative Construction:

• Initialize the list ans with [“0”, “1”], representing binary strings of length 1.
• For each subsequent length up to n:
• – Create a temporary list cur to store the new strings.
• – For each string x in ans:
• —- If x ends with ‘1’, append x + “0” to cur (adding ‘0’ is safe).
• —- Always append x + “1” to cur (adding ‘1’ is always safe).
• – Update ans to cur for the next iteration.
• Return the Result

The provided Python solution efficiently generates all binary strings of a given length n without adjacent zeros using an iterative approach. This method ensures that all constraints are met while constructing the strings step by step.

The time and space complexity of the provided solution for generating binary strings of length n without adjacent zeros can be analyzed as follows:

Time Complexity

The algorithm constructs all valid binary strings iteratively, starting from length 1 up to length n. At each iteration, it generates new strings by appending ‘0’ or ‘1’ to existing strings, ensuring no two consecutive ‘0’s are present.

In the worst case, the number of valid binary strings of length n approaches 2^n. This is because each position in the string has two possibilities (‘0’ or ‘1’), leading to 2^n combinations. However, the constraint of no adjacent zeros slightly reduces this number, but it remains exponential in nature.

Therefore, the time complexity is O(n * 2^n). The factor n accounts for the time to append characters and check the last character of each string during each iteration.

Space Complexity

The space complexity is determined by the storage required for all valid strings generated. In the worst case, there are up to 2^n valid strings, each of length n. Thus, the space needed to store all strings is O(n * 2^n).

Additionally, the iterative approach uses temporary lists to store intermediate results, but their space usage is also bounded by O(n * 2^n), as they store subsets of the final output.

In summary, both the time and space complexities of the solution are O(n * 2^n), reflecting the exponential growth in the number of valid binary strings as n increases.

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) —