Last Updated: 18 Nov, 2020
Binary strings with no consecutive 1s.
Moderate
Asked in companies
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
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.
Approaches
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’.