New update is available. Click here to update.

Last Updated: 11 Jan, 2021

Difficulty: Moderate

```
The first line contains an integer 'T' denoting the number of test cases.
The first line and the only line of each test case contains a string 'STR' containing β1β, β0β, and β?β only.
```

```
For each test case, return all the possible strings in a sorted order(from lexicographically smallest to largest) that can be generated in the manner as described in the problem statement.
```

```
1. You donβt need to print anything, It has already been taken care of. Just implement the given function.
2. It is guaranteed that the number of special characters will not be more than 14.
```

```
1 <= T <= 50
1 <= |STR| <= 30
Where '|STR|' denotes the length of the string 'STR'.
Time limit: 1 sec
```

In this approach we will be using recursion to reach all the possible binary strings.

We will start by making a function named binaryStrings(). Inside this, we will make an integer variable named index(initialised to be 0).

- Now we check if the index is equal to the length of the string, if this condition is met we simply print that string.
- Also, we check if the current character i.e βSTR[index]β is equal to β?β or not. If it is equal to β?β, then we replace β?β with both 0 and 1 and at the same time increment the index by 1.
- We then recursively call the function again but this time the index is 1 more than the previous call.
- If the current character i.e βSTR[index]β was not equal to β?β, then also we increment index by 1 and call the function again recursively.

For example: 1?0

- We start traversing the indices of the string till we find β?β. On reaching the second index we encounter a β?β.
- We then replace β?β with 0(new string becomes 100) and recursively call the function again with index = 3 this time.
- Similarly, we replace β?β with 1(new string becomes 110) and recursively call the function again with index = 3 this time.
- Now we see that our index is equal to the length of the string(100), hence we print 100.
- Similarly, we see that our index is equal to the length of the string(110), hence we print 110.

In this approach we will be reaching all the possible binary strings iteratively. Can you guess what data structure weβll be using here? We will be using queue data structure to do this. We can also use stack, vector or any empty container to do this.

The steps are as follows:

- We will find the position of the very first occurrence of β?β in the given string.
- We will replace this β?β by β0β, then by β1β and push both of these strings into the queue.
- We then pop the next string from the queue.
- We repeat this process till the queue is empty.
- If no β?β are left, we just print the string.

For example: 1?0

- We start traversing the indices of the string till we find β?β. On reaching the second index we encounter a β?β.
- We then replace β?β by 0 and push 100 in the queue.
- Similarly, we replace β?β by 1 and push 110 in the queue.
- Finally, when no β?β are left, we simply print 100 and 110.

Popular Interview Problems: