Generate all binary strings of length n with sub | Utility function to print the given binary string ; This function will be called recursively to generate the next bit for given binary string according to its current state ; Base - case : if the generated binary string meets the required length and the pattern "01" appears twice ; nextbit needs to be 0 because each time we call the function recursively , we call 2 times for 2 cases : next bit is 0 or 1 The is to assure that the binary string is printed one time only ; Generate the next bit for str and call recursive ; Assign first bit ; The next generated bit will either be 0 or 1 ; If pattern "01" occurrence is < 2 ; Set next bit ; If pattern "01" appears then increase the occurrence of pattern ; Else pattern "01" occurrence equals 2 ; If previous bit is 0 then next bit cannot be 1 ; Otherwise ; Driver code ; Length of the resulting strings must be at least 4 ; Generate all binary strings of length n with sub - string "01" appearing twice
def printBinStr ( string , length ) : NEW_LINE INDENT for i in range ( 0 , length ) : NEW_LINE INDENT print ( string [ i ] , end = " " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def generateBinStr ( string , length , currlen , occur , nextbit ) : NEW_LINE INDENT if currlen == length : NEW_LINE INDENT if occur == 2 and nextbit == 0 : NEW_LINE INDENT printBinStr ( string , length ) NEW_LINE DEDENT return NEW_LINE DEDENT if currlen == 0 : NEW_LINE INDENT string [ 0 ] = nextbit NEW_LINE generateBinStr ( string , length , currlen + 1 , occur , 0 ) NEW_LINE generateBinStr ( string , length , currlen + 1 , occur , 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT if occur < 2 : NEW_LINE INDENT string [ currlen ] = nextbit NEW_LINE if string [ currlen - 1 ] == 0 and nextbit == 1 : NEW_LINE INDENT occur += 1 NEW_LINE DEDENT generateBinStr ( string , length , currlen + 1 , occur , 0 ) NEW_LINE generateBinStr ( string , length , currlen + 1 , occur , 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT if string [ currlen - 1 ] == 0 and nextbit == 1 : NEW_LINE INDENT return NEW_LINE DEDENT else : NEW_LINE INDENT string [ currlen ] = nextbit NEW_LINE generateBinStr ( string , length , currlen + 1 , occur , 0 ) NEW_LINE generateBinStr ( string , length , currlen + 1 , occur , 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 NEW_LINE if n < 4 : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT string = [ None ] * n NEW_LINE generateBinStr ( string , n , 0 , 0 , 0 ) NEW_LINE generateBinStr ( string , n , 0 , 0 , 1 ) NEW_LINE DEDENT DEDENT