Minimal String Xoration (Codeforces 1654F)
Tags: Greedy, hashing

You are given an integer $$$n$$$ and a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet. The characters of the string $$$s$$$ are $$$s_0s_1s_2\cdots s_{2^n-1}$$$.A string $$$t$$$ of length $$$2^n$$$ (whose characters are denoted by $$$t_0t_1t_2\cdots t_{2^n-1}$$$) is a xoration of $$$s$$$ if there exists an integer $$$j$$$ ($$$0\le j \leq 2^n-1$$$) such that, for each $$$0 \leq i \leq 2^n-1$$$, $$$t_i = s_{i \oplus j}$$$ (where $$$\oplus$$$ denotes the operation bitwise XOR).Find the lexicographically minimal xoration of $$$s$$$.A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:   $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;  in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.  

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 18$$$).The second line contains a string $$$s$$$ consisting of $$$2^n$$$ lowercase letters of the English alphabet.

Output: Print a single line containing the lexicographically minimal xoration of $$$s$$$.

Note: In the first test, the lexicographically minimal xoration $$$t$$$ of $$$s =$$$"acba" is "abca". It's a xoration because, for $$$j = 3$$$,   $$$t_0 = s_{0 \oplus j} = s_3 =$$$ "a";  $$$t_1 = s_{1 \oplus j} = s_2 =$$$ "b";  $$$t_2 = s_{2 \oplus j} = s_1 =$$$ "c";  $$$t_3 = s_{3 \oplus j} = s_0 =$$$ "a".  There isn't any xoration of $$$s$$$ lexicographically smaller than "abca".In the second test, the minimal string xoration corresponds to choosing $$$j = 4$$$ in the definition of xoration.In the third test, the minimal string xoration corresponds to choosing $$$j = 11$$$ in the definition of xoration.In the fourth test, the minimal string xoration corresponds to choosing $$$j = 10$$$ in the definition of xoration.In the fifth test, the minimal string xoration corresponds to choosing either $$$j = 0$$$ or $$$j = 1$$$ in the definition of xoration.

Sample Inputs:
2
acba

3
bcbaaabb

4
bdbcbccdbdbaaccd

5
ccfcffccccccffcfcfccfffffcccccff

1
zz

Sample Outputs:
abca

aabbbcba

abdbdccacbdbdccb

cccccffffcccccffccfcffcccccfffff

zz

Solution (Python):
r = range
n = int(input())
N = 1 << n
s = input()
a = sorted([ord(s[i]) * N + i for i in r(N)])
for j in r(n):
    p = 1 << j
    v = [0] * N
    c = 0
    l = 0
    for i in r(N):
        if a[i] // N > c:
            c = a[i] // N
            l += 1
        v[a[i] % N] = l
    a = sorted([v[i] * N * N + v[i ^ p] * N + i for i in r(N)])
print(''.join([s[j ^ a[0] % N] for j in r(N)]))

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
import time
(n,) = I()
N = 1 << n
N2 = N ** 2
s = input()
alpha = 'abcdefghijklmnopqrstuvwxyz'
adict = {alpha[i]: i for i in range(26)}
a = [adict[s[i]] * N + i for i in range(N)]
a.sort()
for j in range(n):
    power = 1 << j
    v = [0] * N
    curr = a[0] // N
    val = 0
    for i in range(N):
        if a[i] // N > curr:
            curr = a[i] // N
            val += 1
        v[a[i] % N] = val
    a = sorted([v[i] * N2 + v[i ^ power] * N + i for i in range(N)])
i = a[0] % N
l = []
for j in range(N):
    l.append(s[j ^ i])
print(''.join(l))

Solution (Python):
r = range
n = int(input())
N = 1 << n
s = input()
a = sorted([ord(s[i]) * N + i for i in r(N)])
for j in r(n):
    p = 1 << j
    v = [0] * N
    c = 0
    l = 0
    for i in r(N):
        if a[i] // N > c:
            c = a[i] // N
            l += 1
        v[a[i] % N] = l
    a = sorted([v[i] * N * N + v[i ^ p] * N + i for i in r(N)])
print(''.join([s[j ^ a[0] % N] for j in r(N)]))