XOR Palindromes (Codeforces 1867B)
Tags: Others, strings

You are given a binary string $$$s$$$ of length $$$n$$$ (a string that consists only of $$$0$$$ and $$$1$$$). A number $$$x$$$ is good if there exists a binary string $$$l$$$ of length $$$n$$$, containing $$$x$$$ ones, such that if each symbol $$$s_i$$$ is replaced by $$$s_i \oplus l_i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation), then the string $$$s$$$ becomes a palindrome.You need to output a binary string $$$t$$$ of length $$$n+1$$$, where $$$t_i$$$ ($$$0 \leq i \leq n$$$) is equal to $$$1$$$ if number $$$i$$$ is good, and $$$0$$$ otherwise.A palindrome is a string that reads the same from left to right as from right to left. For example, 01010, 1111, 0110 are palindromes.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, output a single line containing a binary string $$$t$$$ of length $$$n+1$$$ - the answer to the problem.

Note: Consider the first example.   $$$t_2 = 1$$$ because we can choose $$$l = $$$ 010100, then the string $$$s$$$ becomes 111111, which is a palindrome.  $$$t_4 = 1$$$ because we can choose $$$l = $$$ 101011.  It can be shown that for all other $$$i$$$, there is no answer, so the remaining symbols are $$$0$$$. 

Sample Inputs:
5
6
101011
5
00000
9
100100011
3
100
1
1

Sample Outputs:
0010100
111111
0011111100
0110
11

Solution (Python):
import sys
input = sys.stdin.readline
for i in range(int(input())):
    n = int(input())
    s = input()
    c = 0
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            c += 1
    if n % 2:
        sys.stdout.write('0' * c + '1' * (n - 2 * c + 1) + '0' * c + '\n')
    else:
        sys.stdout.write('0' * c + '10' * ((n - 2 * c) // 2) + '1' + '0' * c + '\n')

Solution (Python):
import sys
input = sys.stdin.readline
for i in range(int(input())):
    n = int(input())
    s = input()
    c = 0
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            c += 1
    if n % 2:
        sys.stdout.write('0' * c + '1' * (n - 2 * c + 1) + '0' * c + '\n')
    else:
        sys.stdout.write('0' * c + '10' * ((n - 2 * c) // 2) + '1' + '0' * c + '\n')

Solution (Python):
import sys
input = sys.stdin.readline
for t in range(int(input())):
    n = int(input())
    s = input()
    c = 0
    for i in range(n // 2):
        if s[i] != s[n - i - 1]:
            c += 1
    if c == 0:
        if n % 2:
            print('1' * (n + 1))
        else:
            print('10' * (n // 2) + '1')
    else:
        ans = ['0'] * (n + 1)
        can = n - 2 * c
        if n % 2:
            ans = '0' * c + '11' + '11' * (can // 2) + '0' * (n + 1 - c - 2 - can // 2 * 2)
        else:
            ans = '0' * c + '1' + '01' * (can // 2) + '0' * (n + 1 - c - 1 - can // 2 * 2)
        print(ans)