Binary strings with no consecutive 1s.

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
168 upvotes
Asked in companies
Wells FargoAmazonGoogle inc

Problem statement

You have been given an integer 'N'. Your task is to generate and return all binary strings of length 'N' such that there are no consecutive 1's in the string.


A binary string is that string which contains only ‘0’ and ‘1’.


For Example: 
Let ‘N'=3, hence the length of the binary string would be 3. 

We can have the following binary strings with no consecutive 1s:
000 001 010 100 101
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains a single integer 'N' denoting the length of the binary string to be generated.
Output Format 
All possible binary strings without consecutive ‘1’ of the length 'N' will be printed in lexicographically increasing order.
Note: 
You don't need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
4
Sample Output 1:
0000 0001 0010 0100 0101 1000 1001 1010
Explanation of sample input 1:
For N = 4 we get the following Strings:

0000 0001 0010 0100 0101 1000 1001 1010 

Note that none of the strings has consecutive 1s. Also, note that they are in a lexicographically increasing order.
Sample Input 2:
2
Sample Output 2:
00 01 10
Constraints:
1 <= 'N' <= 20

Time limit: 1 second
Hint

Recursively generate all possible strings that satisfy the condition

Approaches (1)
Recursive Approach

Since we need to generate all substrings which does not have consecutive 1s we can simply start adding new characters to the string until the length of the string is ‘K’ taking care that if the last character of the current string is ‘1’ we cannot add another ‘1’ as it will result in consecutive ‘1s.’ Otherwise, if the last character is ‘0’ we have 2 options either to add ‘1’ or ‘0’. We explore both the options recursively until we have a string of desired length i.e ‘K’ .

 

  • We start with a string of length 1. Now we have 2 options, the first character can be a ‘1’  or a ‘0’.
  • We take both possibilities and use our recursive function to find the answer.

 

Our recursive function works as follows:

  • Check the last character of the string. If the last character is ‘0’ we can add a ‘0’ or ‘1’ at the end of the string.
  • If the last character is ‘1’ we can add only ‘0’ and not ‘1’ because if we add ‘1’ and the last character is also ‘1’ we will violate the condition that there must be no consecutive ‘1’ in the string.
  • Once the length of the string is equal to ‘K’ we add it to our answer array.
  • Lastly, we sort the array and return all possible strings of length ‘K’ with no consecutive ‘1’.
Time Complexity

O(2 ^ N), ‘N’ is the length of the string.

 

For every character, we have 2 choices either put a ‘0’ or a ‘1’ hence for ‘N’ choices we will have a total time complexity of order of O(2 ^ N)

Space Complexity

O(N), ‘N’ is the length of the string

 

The recursive stack uses space of the order O(N).

Code Solution
(100% EXP penalty)
Binary strings with no consecutive 1s.
Full screen
Console