Best Binary String (Codeforces 1837C)
Tags: Greedy, constructive algorithms

You are given a string $$$s$$$ consisting of the characters 0, 1 and/or ?. Let's call it a pattern.Let's say that the binary string (a string where each character is either 0 or 1) matches the pattern if you can replace each character ? with 0 or 1 (for each character, the choice is independent) so that the strings become equal. For example, 0010 matches ?01?, but 010 doesn't match 1??, ??, or ????.Let's define the cost of the binary string as the minimum number of operations of the form "reverse an arbitrary contiguous substring of the string" required to sort the string in non-descending order.You have to find a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of test cases.The first and only line of each test case contains the string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$) consisting of characters 0, 1, and/or ?.The sum of the string lengths over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them.

Note: In the first test case of the example, the cost of the resulting string is $$$0$$$.In the second test case, the cost of the resulting string is $$$2$$$: we can reverse the substring from the $$$1$$$-st character to the $$$5$$$-th character, and we obtain the string 00101. Then we reverse the substring from the $$$3$$$-rd to the $$$4$$$-th character, and we obtain the string 00011, which is sorted in non-descending order.

Sample Inputs:
4
??01?
10100
1??10?
0?1?10?10

Sample Outputs:
00011
10100
111101
011110010

Solution (Python):
import sys

def main():
    cases = int(sys.stdin.readline().strip())
    for _ in range(cases):
        s = sys.stdin.readline().strip()
        print(solve(s))

def solve(s: str) -> str:
    sol = []
    for char in s:
        if char == '?':
            if sol:
                sol.append(sol[-1])
            else:
                sol.append('0')
        else:
            sol.append(char)
    return ''.join(sol)
main()

Solution (Python):
import random
import sys
from types import GeneratorType
RANDOM = random.randint(1, 10 ** 9)

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def read_str():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def read_int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def read_float():
        return float(sys.stdin.readline().rstrip())

    @staticmethod
    def read_ints():
        return map(int, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_floats():
        return map(float, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_ints_minus_one():
        return map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split())

    @staticmethod
    def read_list_ints():
        return list(map(int, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_floats():
        return list(map(float, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_ints_minus_one():
        return list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))

    @staticmethod
    def read_list_strs():
        return sys.stdin.readline().rstrip().split()

    @staticmethod
    def read_list_str():
        return list(sys.stdin.readline().rstrip())

    @staticmethod
    def st(x):
        return print(x)

    @staticmethod
    def lst(x):
        return print(*x)

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, queue=[]):

        def wrappedfunc(*args, **kwargs):
            if queue:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        queue.append(to)
                        to = next(to)
                    else:
                        queue.pop()
                        if not queue:
                            break
                        to = queue[-1].send(to)
                return to
        return wrappedfunc

    def ask(self, lst):
        self.lst(lst)
        sys.stdout.flush()
        res = self.read_int()
        return res

    @staticmethod
    def accumulate(nums):
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]
        return pre

class Wrapper(int):

    def __init__(self, x):
        int.__init__(x)

    def __hash__(self):
        return super(Wrapper, self).__hash__() ^ RANDOM

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        for _ in range(ac.read_int()):
            s = ac.read_str()
            ans = ''
            pre = '0'
            for w in s:
                if w == '?':
                    ans += pre
                else:
                    pre = w
                    ans += w
            ac.st(ans)
        return
Solution().main()

Solution (Python):
import sys
import math
from collections import Counter

def II():
    return int(sys.stdin.readline())

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LS():
    return sys.stdin.readline().strip().split()

def SI():
    return sys.stdin.readline().strip()

def MIN_INT():
    return -1 * sys.maxsize

def MAX_INT():
    return sys.maxsize
MOD = 1000000007
''

def solve():
    s = list(SI())
    n = len(s)
    if s[0] == '?':
        s[0] = '0'
    if s[-1] == '?':
        s[-1] = '1'
    for i in range(1, n - 1):
        if s[i] == '?':
            if s[i + 1] == '1' or s[i - 1] == '1':
                s[i] = '1'
            else:
                s[i] = '0'
    print(''.join(s))

def main():
    t = II()
    for _ in range(t):
        solve()
main()