Teaching Kids Programming – Generate Binary Strings Without Adjacent Zeros (Recursive Depth First Search Algorithm)

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

Hints:
If we have a string s of length x, we can generate all strings of length x + 1.
If s has 0 as the last character, we can only append 1, whereas if the last character is 1, we can append both 0 and 1.
We can use recursion and backtracking to generate all such strings.

Generate Binary Strings Without Adjacent Zeros (Recursive Depth First Search Algorithm)

A brute-force solution would be to generate all possible binary strings of length n (which has a time complexity of O(2^n)) and then check each one to see if it is valid (i.e., contains no consecutive zeros). This results in an overall time complexity of O(n * 2^n), which is inefficient and far from optimal.

A more efficient approach uses a DFS (Depth First Search) algorithm to explore the solution space. The idea is to build the binary string incrementally, ensuring that we never add two consecutive zeros. Specifically, if the current node (last character) is “0”, the next character must be “1”. If the last character is “1”, we can add either “0” or “1”. This method skips invalid combinations (e.g., strings containing “00”) as they are constructed, rather than generating all possibilities and filtering them afterward.

The time and space complexity of this approach is O(2^n). This is because the DFS explores a binary tree where each node either adds a “0” or “1”, leading to 2^n total paths.

Here’s the implementation of the Depth First Search algorithm using Recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def validStrings(self, n: int) -> List[str]:
 
        def dfs(cur):
            if len(cur) == n:
                self.ans.append("".join(cur))
                return
            if len(cur) == 0 or cur[-1] == '1':
                dfs(cur + ["0"])
            dfs(cur + ["1"])
        
        self.ans = []
        dfs([])
        return self.ans

class Solution:
    def validStrings(self, n: int) -> List[str]:

        def dfs(cur):
            if len(cur) == n:
                self.ans.append("".join(cur))
                return
            if len(cur) == 0 or cur[-1] == '1':
                dfs(cur + ["0"])
            dfs(cur + ["1"])
        
        self.ans = []
        dfs([])
        return self.ans

Of course, we can explore the search tree using Breadth First Search Algorithm where the nodes are visited in the level order and the children nodes are expanded level by level as well.

Generate Binary Strings Without Adjacent Zeros

• Teaching Kids Programming - Generate Binary Strings Without Adjacent Zeros (Recursive Depth First Search Algorithm)

–EOF (The Ultimate Computing & Technology Blog) —