Count algorithm

I am looking for an algorithm that counts a given number of states in Python.
There is a string like this: 10?01?011
with "0, 1, ?" it was made. The question mark can be 0 or 1. The program should enumerate all the states that question marks can have in a string.
For example, in the program '1?01?1' should be printed:

110111
110101
100111
100101

Note: The order does not matter.

I'm thinking about this algorithm but I can't find the optimal algorithm for this problem in Python.Does anyone know how I can create an algorithm for this in Python?
I am looking for this algorithm in Python without using libraries.

You can use the following generator function:

from itertools import product  # or use `product` function from below

def states(s):
    for tpl in product("01", repeat=s.count("?")):
        gaps = iter(tpl)  # iterator over the product tuple 
        yield "".join(next(gaps) if c == "?" else c for c in s)

list(states("1?01?1"))
# ['100101', '100111', '110101', '110111']
list(states("???"))
# ['000', '001', '010', '011', '100', '101', '110', '111']
list(states("11?"))
# ['110', '111']
list(states("11"))
# ['11']

You form the cartesian product of "01" x "01" x ... x "01" for as how many gaps there are. Then you repeatedly fill the gaps with the tuples of the product.

You can write your own product function as a drop-in replacement if libraries aren't allowed:

def product(pool, repeat=1):
    if not repeat:
        yield []
    else:
        for elmnt in pool:
            for tpl in product(pool, repeat-1):
                yield [elmnt] + tpl

There is another implementation of product in the itertools.product docs.

Expanding by one chacracter at a time:

<!-- language-all: lang-python -->

<pre><code>s = '1?01?1'

ss = ['']
for c in s:
if c == '?':
c = '01'
ss =

for s in ss:
print(s)
</code></pre>

Output (Try it online!):

TIO-ljbjo7ry: https://tio.run/##TYwxDoAgDEX3nuJv1bhIXIyJ4SDGCWNkQUJdPD1SWPzTf21f4/tcd5jmmHIWrGBjR2MNE4nixrzTeSc4@ABZCCX@LLiWW8ttoHEqj0VUaK5gwAG1pdpS@6Hd7US/RXsTkw9PJz1Rzh8 "Python 3.8 (pre-release) – Try It Online"

100101
100111
110101
110111