Generate all binary strings of length n with sub-string β01β appearing exactly twice
Given an integer N, the task is to generate all possible binary strings of length N which contain β01β as the sub-string exactly twice.
Examples:
Input: N = 4
Output:
0101
β0101β is the only binary string of length 4
that contains β01β exactly twice as the sub-string.Input: N = 5
Output:
00101
01001
01010
01011
01101
10101
Approach: This problem can solved using backtracking. To generate a binary string, we implement a function that generate each bit at a time, update the state of the binary string (current length, number of occurrences of the pattern). Then call the function recursively, and according to the current state of the binary string, the function will decide how to generate the next bit or print out the binary string (if the problemβs requirement is met).
For this problem, backtracking strategy looks like we generate a binary tree with each node can have either value 0 or 1.
For example, with N = 4, the tree will look like:
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> #include <stdlib.h> using namespace std; // Utility function to print the given binary string void printBinStr( int * str, int len) { for ( int i = 0; i < len; i++) { cout << str[i]; } cout << endl; } // This function will be called recursively // to generate the next bit for given // binary string according to its current state void generateBinStr( int * str, int len, int currlen, int occur, int nextbit) { // Base-case: if the generated binary string // meets the required length and the pattern "01" // appears twice if (currlen == len) { // 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 if (occur == 2 && nextbit == 0) printBinStr(str, len); return ; } // Generate the next bit for str // and call recursive if (currlen == 0) { // Assign first bit str[0] = nextbit; // The next generated bit will either be 0 or 1 generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } else { // If pattern "01" occurrence is < 2 if (occur < 2) { // Set next bit str[currlen] = nextbit; // If pattern "01" appears then // increase the occurrence of pattern if (str[currlen - 1] == 0 && nextbit == 1) { occur += 1; } generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); // Else pattern "01" occurrence equals 2 } else { // If previous bit is 0 then next bit cannot be 1 if (str[currlen - 1] == 0 && nextbit == 1) { return ; // Otherwise } else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } } } } // Driver code int main() { int n = 5; // Length of the resulting strings // must be at least 4 if (n < 4) cout << -1; else { int * str = new int [n]; // Generate all binary strings of length n // with sub-string "01" appearing twice generateBinStr(str, n, 0, 0, 0); generateBinStr(str, n, 0, 0, 1); } return 0; } |
Java
// Java implementation of the above approach class GFG { // Utility function to print the given binary string static void printBinStr( int [] str, int len) { for ( int i = 0 ; i < len; i++) { System.out.print(str[i]); } System.out.println(); } // This function will be called recursively // to generate the next bit for given // binary string according to its current state static void generateBinStr( int [] str, int len, int currlen, int occur, int nextbit) { // Base-case: if the generated binary string // meets the required length and the pattern "01" // appears twice if (currlen == len) { // 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 if (occur == 2 && nextbit == 0 ) { printBinStr(str, len); } return ; } // Generate the next bit for str // and call recursive if (currlen == 0 ) { // Assign first bit str[ 0 ] = nextbit; // The next generated bit will either be 0 or 1 generateBinStr(str, len, currlen + 1 , occur, 0 ); generateBinStr(str, len, currlen + 1 , occur, 1 ); } else // If pattern "01" occurrence is < 2 if (occur < 2 ) { // Set next bit str[currlen] = nextbit; // If pattern "01" appears then // increase the occurrence of pattern if (str[currlen - 1 ] == 0 && nextbit == 1 ) { occur += 1 ; } generateBinStr(str, len, currlen + 1 , occur, 0 ); generateBinStr(str, len, currlen + 1 , occur, 1 ); // Else pattern "01" occurrence equals 2 } else // If previous bit is 0 then next bit cannot be 1 if (str[currlen - 1 ] == 0 && nextbit == 1 ) { return ; // Otherwise } else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1 , occur, 0 ); generateBinStr(str, len, currlen + 1 , occur, 1 ); } } // Driver code public static void main(String[] args) { int n = 5 ; // Length of the resulting strings // must be at least 4 if (n < 4 ) { System.out.print(- 1 ); } else { int [] str = new int [n]; // Generate all binary strings of length n // with sub-string "01" appearing twice generateBinStr(str, n, 0 , 0 , 0 ); generateBinStr(str, n, 0 , 0 , 1 ); } } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Utility function to print the # given binary string def printBinStr(string, length): for i in range ( 0 , length): print (string[i], end = "") print () # This function will be called recursively # to generate the next bit for given # binary string according to its current state def generateBinStr(string, length, currlen, occur, nextbit): # Base-case: if the generated binary # string meets the required length and # the pattern "01" appears twice if currlen = = length: # 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 if occur = = 2 and nextbit = = 0 : printBinStr(string, length) return # Generate the next bit for # str and call recursive if currlen = = 0 : # Assign first bit string[ 0 ] = nextbit # The next generated bit will # either be 0 or 1 generateBinStr(string, length, currlen + 1 , occur, 0 ) generateBinStr(string, length, currlen + 1 , occur, 1 ) else : # If pattern "01" occurrence is < 2 if occur < 2 : # Set next bit string[currlen] = nextbit # If pattern "01" appears then # increase the occurrence of pattern if string[currlen - 1 ] = = 0 and nextbit = = 1 : occur + = 1 generateBinStr(string, length, currlen + 1 , occur, 0 ) generateBinStr(string, length, currlen + 1 , occur, 1 ) # Else pattern "01" occurrence equals 2 else : # If previous bit is 0 then next bit cannot be 1 if string[currlen - 1 ] = = 0 and nextbit = = 1 : return # Otherwise else : string[currlen] = nextbit generateBinStr(string, length, currlen + 1 , occur, 0 ) generateBinStr(string, length, currlen + 1 , occur, 1 ) # Driver code if __name__ = = "__main__" : n = 5 # Length of the resulting strings # must be at least 4 if n < 4 : print ( - 1 ) else : string = [ None ] * n # Generate all binary strings of length n # with sub-string "01" appearing twice generateBinStr(string, n, 0 , 0 , 0 ) generateBinStr(string, n, 0 , 0 , 1 ) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the above approach using System; class GFG { // Utility function to print the given binary string static void printBinStr( int [] str, int len) { for ( int i = 0; i < len; i++) { Console.Write(str[i]); } Console.Write( "\n" ); } // This function will be called recursively // to generate the next bit for given // binary string according to its current state static void generateBinStr( int [] str, int len, int currlen, int occur, int nextbit) { // Base-case: if the generated binary string // meets the required length and the pattern "01" // appears twice if (currlen == len) { // 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 if (occur == 2 && nextbit == 0) { printBinStr(str, len); } return ; } // Generate the next bit for str // and call recursive if (currlen == 0) { // Assign first bit str[0] = nextbit; // The next generated bit will either be 0 or 1 generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } else // If pattern "01" occurrence is < 2 if (occur < 2) { // Set next bit str[currlen] = nextbit; // If pattern "01" appears then // increase the occurrence of pattern if (str[currlen - 1] == 0 && nextbit == 1) { occur += 1; } generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); // Else pattern "01" occurrence equals 2 } else // If previous bit is 0 then next bit cannot be 1 if (str[currlen - 1] == 0 && nextbit == 1) { return ; // Otherwise } else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } } // Driver code public static void Main(String[] args) { int n = 5; // Length of the resulting strings // must be at least 4 if (n < 4) { Console.Write(-1); } else { int [] str = new int [n]; // Generate all binary strings of length n // with sub-string "01" appearing twice generateBinStr(str, n, 0, 0, 0); generateBinStr(str, n, 0, 0, 1); } } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript implementation of the approach // Utility function to print the given binary string function printBinStr(str, len) { for ( var i = 0; i < len; i++) { document.write(str[i]); } document.write( "<br>" ); } // This function will be called recursively // to generate the next bit for given // binary string according to its current state function generateBinStr(str, len, currlen, occur, nextbit) { // Base-case: if the generated binary string // meets the required length and the pattern "01" // appears twice if (currlen == len) { // 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 if (occur == 2 && nextbit == 0) printBinStr(str, len); return ; } // Generate the next bit for str // and call recursive if (currlen == 0) { // Assign first bit str[0] = nextbit; // The next generated bit will either be 0 or 1 generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } else { // If pattern "01" occurrence is < 2 if (occur < 2) { // Set next bit str[currlen] = nextbit; // If pattern "01" appears then // increase the occurrence of pattern if (str[currlen - 1] == 0 && nextbit == 1) { occur += 1; } generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } // Else pattern "01" occurrence equals 2 else { // If previous bit is 0 then next // bit cannot be 1 if (str[currlen - 1] == 0 && nextbit == 1) { return ; } // Otherwise else { str[currlen] = nextbit; generateBinStr(str, len, currlen + 1, occur, 0); generateBinStr(str, len, currlen + 1, occur, 1); } } } } // Driver code var n = 5; // Length of the resulting strings // must be at least 4 if (n < 4) document.write(-1); else { var str = Array(n); // Generate all binary strings of length n // with sub-string "01" appearing twice generateBinStr(str, n, 0, 0, 0); generateBinStr(str, n, 0, 0, 1); } // This code is contributed by importantly </script> |
00101 01001 01010 01011 01101 10101
Time Complexity: O(2^n)
Auxiliary Space: O(2^n)
Approach 2:
Using an iterative method to generate all binary strings of length n
Step-by-step Explanation:
- Use a for loop to iterate over all integers from 0 to 2^n β 1.
- For each integer i, use the bitset class to convert it to a binary string of length n.
- Use the find method of the string class to check if the binary string contains the substring β01β exactly twice.
- If the binary string contains the substring β01β exactly twice, print it.
C++
#include <iostream> #include <bitset> using namespace std; int main() { int n = 5; if (n < 4) cout << -1 << endl; else { for ( int i = 0; i < (1 << n); i++) { string s = bitset<32>(i).to_string(); s = s.substr(32 - n); size_t first = s.find( "01" ); size_t second = s.find( "01" , first + 2); if (first != string::npos && second != string::npos && s.find( "01" , second + 2) == string::npos) cout << s << endl; } } return 0; } |
Java
import java.util.BitSet; public class GFG { public static void main(String[] args) { int n = 5 ; if (n < 4 ) System.out.println(- 1 ); else { for ( int i = 0 ; i < ( 1 << n); i++) { String s = Integer.toBinaryString(i); while (s.length() < n) { s = "0" + s; } String subsequence = "01" ; int first = s.indexOf(subsequence); int second = s.indexOf(subsequence, first + 2 ); if (first != - 1 && second != - 1 && s.indexOf(subsequence, second + 2 ) == - 1 ) { System.out.println(s); } } } } } |
Python
def print_binary_combinations(n): if n < 4 : print ( - 1 ) else : # Loop through all numbers from 0 to 2^n - 1 for i in range ( 1 << n): # Convert the current number to a binary string of length n binary_str = format (i, '0' + str (n) + 'b' ) # Get the substring of the binary string, excluding leading zeros binary_str = binary_str[ - n:] # Find the first occurrence of "01" in the binary string first = binary_str.find( "01" ) # Find the second occurrence of "01" in the binary string, starting from the position after the first occurrence second = binary_str.find( "01" , first + 2 ) # Check if both occurrences of "01" exist and no other occurrence is present after the second occurrence if first ! = - 1 and second ! = - 1 and binary_str.find( "01" , second + 2 ) = = - 1 : print (binary_str) # Example usage n = 5 print_binary_combinations(n) |
C#
using System; class GFG { static void Main() { int n = 5; if (n < 4) Console.WriteLine(-1); else { for ( int i = 0; i < (1 << n); i++) { string s = Convert.ToString(i, 2).PadLeft( n, '0' ); int first = s.IndexOf( "01" ); int second = s.IndexOf( "01" , first + 2); if (first != -1 && second != -1 && s.IndexOf( "01" , second + 2) == -1) Console.WriteLine(s); } } } } |
Javascript
const n = 5; if (n < 4) { // If n is less than 4, no valid string can be formed console.log(-1); } else { // Loop through all possible combinations of n-bit strings for (let i = 0; i < (1 << n); i++) { // Convert integer to binary string and ensure n bits let s = (i >>> 0).toString(2).padStart(32, '0' ); s = s.substr(32 - n); // Find the indices of the first two occurrences of "01" const first = s.indexOf( "01" ); const second = s.indexOf( "01" , first + 2); // Check if the pattern "01" occurs exactly three times if (first !== -1 && second !== -1 && s.indexOf( "01" , second + 2) === -1) { // Print the valid string console.log(s); } } } |
00101 01001 01010 01011 01101 10101
Time Complexity: O(2^n * n), where n is the length of the binary strings.
Auxiliary Space: O(n), where n is the length of the binary strings.
The time complexity is O(2^n * n) because the algorithm needs to generate all 2^n binary strings of length n and check each string for the substring β01β. The auxiliary space complexity is O(n) because the algorithm needs to store a single binary string at a time, and the length of a binary string is n.
How is this approach different from another approach?
The main difference between the original approach and the alternative approach using an iterative method is the way the binary strings are generated.
In the original approach, binary strings are generated recursively by calling the generateBinStr function. This function generates the next bit for a given binary string according to its current state and calls itself recursively to generate the remaining bits. This approach requires keeping track of the current length of the binary string, the number of occurrences of the substring β01β, and the next bit to be generated.
In contrast, the alternative approach using an iterative method generates binary strings by iterating over all integers from 0 to 2^n β 1 and converting each integer to a binary string using the bitset class. This approach is simpler and easier to understand because it doesnβt require recursion or keeping track of additional variables.
Both approaches have the same goal of generating all binary strings of length n that contain the substring β01β exactly twice. However, they use different methods to achieve this goal. The original approach has a lower time complexity of O(2^n) because it generates only valid binary strings, while the alternative approach has a higher time complexity of O(2^n * n) because it generates all 2^n binary strings and checks each one for validity.