# Binary Replacement

Write a program that takes in a binary string that also contains x's and prints out all possible binary strings where each x can be replaced with either a 0 or 1.

Example

```
input: 1010
output: [1010]

input: xx
output: [00, 01, 10, 11]

input: 1x0X
output: [1000, 1001, 1100, 1101]
```

**The Idea:** Iterate through the string: when there is an x, append both 0 and 1 to the string, and branch out on each one of these cases. Otherwise just branch by 1.![](/files/-LoJIg24tRHSBE8obdat)

**Complexity:** O(2^n + |S| - n) where n is the number of 'x's, and S is the length of the string.

```python
import queue


def binary_replacement(str):
    if not str:
        return []

    q = queue.Queue()
    q.put(('', -1))
    sol = []

    while not q.empty():
        cum_str, i = q.get()

        if i + 1 >= len(str):
            sol.append(cum_str)
            while not q.empty():
                sol.append(q.get()[0])
            return sol

        cur_char = str[i+1]
        if cur_char == 'x' or cur_char == 'X':
            q.put((cum_str + '0', i + 1))
            q.put((cum_str + '1', i + 1))
        else:
            q.put((cum_str + cur_char, i + 1))


print(binary_replacement('xx'))
print(binary_replacement('1x0X'))
print(binary_replacement('1010'))
```

**Recursive Approach**

```python
def binary_replacement(bx):
    sol = []
    def dfs(i, cur):
        if len(cur) == len(bx):
            sol.append(cur)
            return
        else:
            if bx[i].lower() != 'x':
                dfs(i+1, cur+bx[i])
            else:
                dfs(i+1, cur+'1')
                dfs(i+1, cur+'0')
    dfs(0, '')
    return sol
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/trees-and-graphs/binary-replacement.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.