A-B Palindrome (Codeforces 1512C)
Tags: Others, strings

You are given a string $$$s$$$ consisting of the characters '0', '1', and '?'. You need to replace all the characters with '?' in the string $$$s$$$ by '0' or '1' so that the string becomes a palindrome and has exactly $$$a$$$ characters '0' and exactly $$$b$$$ characters '1'. Note that each of the characters '?' is replaced independently from the others.A string $$$t$$$ of length $$$n$$$ is called a palindrome if the equality $$$t[i] = t[n-i+1]$$$ is true for all $$$i$$$ ($$$1 \le i \le n$$$).For example, if $$$s=$$$"01?????0", $$$a=4$$$ and $$$b=4$$$, then you can replace the characters '?' in the following ways:   "01011010";  "01100110". For the given string $$$s$$$ and the numbers $$$a$$$ and $$$b$$$, replace all the characters with '?' in the string $$$s$$$ by '0' or '1' so that the string becomes a palindrome and has exactly $$$a$$$ characters '0' and exactly $$$b$$$ characters '1'.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.The first line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$0 \le a, b \le 2 \cdot 10^5$$$, $$$a + b \ge 1$$$).The second line of each test case contains the string $$$s$$$ of length $$$a+b$$$, consisting of the characters '0', '1', and '?'.It is guaranteed that the sum of the string lengths of $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output:   "-1", if you can't replace all the characters '?' in the string $$$s$$$ by '0' or '1' so that the string becomes a palindrome and that it contains exactly $$$a$$$ characters '0' and exactly $$$b$$$ characters '1';  the string that is obtained as a result of the replacement, otherwise. If there are several suitable ways to replace characters, you can output any.


Sample Inputs:
9
4 4
01?????0
3 3
??????
1 0
?
2 2
0101
2 2
01?0
0 1
0
0 3
1?1
2 2
?00?
4 3
??010?0

Sample Outputs:
01011010
-1
0
-1
0110
-1
111
1001
0101010

Solution (Python):
import sys

def solve():
    (a, b) = map(int, input().split())
    s = input()
    if a + b != len(s):
        return -1
    res = ['?'] * len(s)
    (i, j) = (0, len(s) - 1)
    q_num = 0
    while i < j:
        x = s[i] + s[j]
        if x in ['01', '10']:
            return -1
        elif x in ['?0', '0?', '00']:
            res[i] = res[j] = '0'
            a -= 2
        elif x in ['?1', '1?', '11']:
            res[i] = res[j] = '1'
            b -= 2
        else:
            q_num += 2
        i += 1
        j -= 1
    if i == j:
        if s[i] == '0':
            a -= 1
        elif s[i] == '1':
            b -= 1
        else:
            q_num += 1
        res[i] = s[i]
    if a < 0 or b < 0:
        return -1
    (i, j) = (0, len(s) - 1)
    while i < j:
        if res[i] == res[j] == '?':
            if a >= 2:
                res[i] = res[j] = '0'
                a -= 2
            elif b >= 2:
                res[i] = res[j] = '1'
                b -= 2
            else:
                return -1
        i += 1
        j -= 1
    if i == j and res[i] == '?':
        if a >= 1:
            res[i] = '0'
        elif b >= 1:
            res[i] = '1'
        else:
            return -1
    return ''.join(res)
t = int(input())
for _ in range(t):
    print(solve())

Solution (Python):
def solve(s, a, b):
    a = a - s.count('0')
    b = b - s.count('1')
    left = 0
    right = len(s) - 1
    same_pairs = []
    result = list(s)
    single = []
    while right >= left:
        if left == right and s[left] == '?':
            single.append(left)
            break
        if s[left] == s[right] and s[left] == '?':
            same_pairs.append((left, right))
        elif s[left] != s[right]:
            if s[left] == '?':
                if s[right] == '0':
                    a -= 1
                    result[left] = '0'
                else:
                    b -= 1
                    result[left] = '1'
            elif s[right] == '?':
                if s[left] == '0':
                    a -= 1
                    result[right] = '0'
                else:
                    b -= 1
                    result[right] = '1'
            else:
                return -1
        left += 1
        right -= 1
    if a < 0 or b < 0:
        return -1
    if single:
        p = a + b - 1
        if p % 2 != 0:
            return -1
        p /= 2
        if p < len(same_pairs):
            return -1
    else:
        if a % 2 != 0:
            return -1
        if b % 2 != 0:
            return -1
        pairs_av = (a + b) // 2
        if pairs_av < len(same_pairs):
            return -1
    for (left, right) in same_pairs:
        if a > 1:
            result[left] = '0'
            result[right] = '0'
            a -= 2
        else:
            result[left] = '1'
            result[right] = '1'
            b -= 2
    for i in single:
        if a > 0:
            result[i] = '0'
            a -= 1
        else:
            result[i] = '1'
            b -= 1
    return ''.join(result)
if __name__ == '__main__':
    tests = int(input())
    for i in range(tests):
        (a, b) = map(int, input().split())
        s = input()
        print(solve(s, a, b))

Solution (Python):
for _ in range(int(input())):
    (zero, one) = map(int, input().split())
    length = zero + one
    text = list(input())
    flag = 1
    for index in range(length // 2):
        if text[index] == text[length - index - 1]:
            if text[index] == '1':
                one -= 2
            elif text[index] == '0':
                zero -= 2
        elif text[index] == '?' and text[length - index - 1] == '1' or (text[index] == '1' and text[length - index - 1] == '?'):
            text[index] = '1'
            text[length - index - 1] = '1'
            one -= 2
        elif text[index] == '?' and text[length - index - 1] == '0' or (text[index] == '0' and text[length - index - 1] == '?'):
            text[index] = '0'
            text[length - index - 1] = '0'
            zero -= 2
        else:
            flag = 0
            break
    if flag == 0 or zero < 0 or one < 0:
        print(-1)
    else:
        for index in range(length // 2):
            if text[index] == '?':
                if zero > one:
                    text[index] = '0'
                    text[length - index - 1] = '0'
                    zero -= 2
                else:
                    text[index] = '1'
                    text[length - index - 1] = '1'
                    one -= 2
        if length % 2 == 1:
            if text[length // 2] == '?':
                if zero > one:
                    text[length // 2] = '0'
                    zero -= 1
                else:
                    text[length // 2] = '1'
                    one -= 1
            elif text[length // 2] == '1':
                one -= 1
            else:
                zero -= 1
        if zero != 0 and one != 0:
            print(-1)
        else:
            print(''.join(text))