Double Lexicographically Minimum (Codeforces 1799C)
Tags: Greedy, strings

You are given a string $$$s$$$. You can reorder the characters to form a string $$$t$$$. Define $$$t_{\mathrm{max}}$$$ to be the lexicographical maximum of $$$t$$$ and $$$t$$$ in reverse order.Given $$$s$$$ determine the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ 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 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. Descriptions of test cases follow.The first and only line of each test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 10^5$$$). $$$s$$$ consists of only lowercase English letters. It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print the lexicographically minimum value of $$$t_{\mathrm{max}}$$$ over all reorderings $$$t$$$ of $$$s$$$. 

Note: For the first test case, there is only one reordering of $$$s$$$, namely "a".For the second test case, there are three reorderings of $$$s$$$.  $$$t = \mathtt{aab}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aab}, \mathtt{baa}) = \mathtt{baa}$$$  $$$t = \mathtt{aba}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{aba}, \mathtt{aba}) = \mathtt{aba}$$$  $$$t = \mathtt{baa}$$$: $$$t_{\mathrm{max}} = \max(\mathtt{baa}, \mathtt{aab}) = \mathtt{baa}$$$ The lexicographical minimum of $$$t_{\mathrm{max}}$$$ over all cases is "aba". 

Sample Inputs:
12
a
aab
abb
abc
aabb
aabbb
aaabb
abbb
abbbb
abbcc
eaga
ffcaba

Sample Outputs:
a
aba
bab
bca
abba
abbba
ababa
bbab
bbabb
bbcca
agea
acffba

Solution (Python):
import string, sys

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input().replace('\n', '')
    return list(s[:len(s)])

def invr():
    return map(int, input().split())

def outp(s):
    sys.stdout.write(s + '\n')

def loutp(l):
    sys.stdout.write(' '.join(map(str, l)) + '\n')

def solve():
    l_ref = {l: i for (i, l) in enumerate(string.ascii_lowercase)}
    n_ref = {i: l for (i, l) in enumerate(string.ascii_lowercase)}
    n = inp()
    for _ in range(n):
        s = insr()
        s = [l_ref[e] for e in s]
        ss = sorted(set(s))
        found_odd = False
        aux = None
        odd_mode = False
        (l, r) = ([], [])
        for e in ss:
            c = s.count(e)
            if odd_mode:
                l = l + [e] * c
            elif found_odd:
                if e == ss[-1]:
                    if c % 2 == 0:
                        l = l + [e] * (c // 2) + [aux]
                    else:
                        l = l + [e] * (c // 2) + [e] + [aux]
                    r = [e] * (c // 2) + r
                else:
                    l = l + [e] * c
                    r = [aux] + r
                    odd_mode = True
            else:
                l = l + [e] * (c // 2)
                r = [e] * (c // 2) + r
                if c % 2 == 1:
                    if e == ss[-1]:
                        l = l + [e]
                    else:
                        aux = e
                        found_odd = True
        mintmax = ''.join([n_ref[e] for e in l + r])
        outp(mintmax)
if __debug__:
    input = sys.stdin.readline
    solve()

Solution (Python):
from collections import defaultdict
import math
import sys
from decimal import Decimal
from math import comb, gcd
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
    return int(input())

def input_list():
    return input().split(' ')

def input_list_int():
    return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
    return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
    global_ans.append(a)

def z_func(s):
    n = len(s)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if r >= i:
            z[i] = min(z[i - l], r - i + 1)
        while z[i] + i < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l = i
            r = i + z[i] - 1
    return z

def is_prime(n):
    d = 2
    while n % d != 0:
        d += 1
    return d == n

def partial_sum(a):
    b = [0]
    for i in a:
        b.append(b[-1] ^ i)
    return b

def partial_sum_2d(a):
    n = len(a)
    if n == 0:
        return []
    m = len(a[0])
    b = []
    for i in range(n + 1):
        b.append([0] * (m + 1))
    for i in range(n):
        for j in range(m):
            b[i + 1][j + 1] = a[i][j] + b[i][j + 1] + b[i + 1][j] - b[i][j]
    return b

def dfs(g, v, s, n):
    visited = [0] * (n + 1)

    def dfs_util(v, s):
        if v == s:
            return 1
        if visited[v]:
            return 0
        visited[v] = 1
        for i in g[v]:
            if not visited[i]:
                lr = dfs_util(i, s)
                if lr:
                    return 1
        return 0
    return dfs_util(v, s)

def bs_down(a, x):
    l = -1
    r = len(a)
    while l + 1 < r:
        m = (l + r) // 2
        if a[m] <= x:
            l = m
        else:
            r = m
    return l

def solve():
    s = [x for x in input()]
    l = len(s)
    s.sort()
    bok = ''
    pos = 0
    while pos + 1 < l:
        if s[pos] == s[pos + 1]:
            bok += s[pos]
        else:
            break
        pos += 2
    bokr = bok[::-1]
    ns = s[len(bok) * 2:]
    tmp = {}
    for i in ns:
        tmp[i] = 1
    if len(tmp) == 0:
        ans = bok + bokr
    elif len(tmp) == 1:
        ans = bok + ''.join(ns) + bokr
    elif len(tmp) == 2:
        t = ns[0]
        cnt = len(ns) // 2
        if len(ns) % 2 == 0:
            t += ns[1]
            cnt -= 1
        bt = cnt * ns[1]
        ans = bok + bt + t + bt[::-1] + bokr
    else:
        ns.append(ns[0])
        ns = ns[1:]
        ans = bok + ''.join(ns) + bokr
    pr(max(ans, ans[::-1]))
query_count = 1
query_count = input_int()
while query_count:
    query_count -= 1
    solve()
for global_ans_line in global_ans:
    if isinstance(global_ans_line, list):
        print(' '.join((str(x) for x in global_ans_line)))
    else:
        print(global_ans_line)

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    s = readStr()
    n = len(s)
    cnt = [0] * 26
    for i in range(n):
        cnt[ord(s[i]) - ord('a')] += 1
    (l, r) = ([], [])
    while len(l) + len(r) < n:
        x = y = -1
        for i in range(26):
            if cnt[i] and x == -1:
                x = i
            elif cnt[i] and y == -1:
                y = i
                break
        (u, v) = (chr(ord('a') + x), chr(ord('a') + y))
        if cnt[x] % 2 == 0:
            l.append(u * (cnt[x] // 2))
            r.append(u * (cnt[x] // 2))
            cnt[x] = 0
        elif y == -1:
            l.append(u * cnt[x])
            cnt[x] = 0
        elif cnt[x] // 2:
            l.append(u * (cnt[x] // 2))
            r.append(u * (cnt[x] // 2))
            cnt[x] = 1
        elif sum(cnt) == cnt[x] + cnt[y]:
            l.append(v * ((cnt[y] + 1) // 2))
            r.append(cnt[y] // 2 * v + u)
            break
        else:
            l.append(v)
            r.append(u)
            cnt[x] -= 1
            cnt[y] -= 1
            for i in range(26):
                l.append(chr(ord('a') + i) * cnt[i])
            break
    ans = ''.join(l) + ''.join(r)[::-1]
    ans = max(ans, ans[::-1])
    return ans
for _ in range(int(input())):
    print(solve())