Minimax (Codeforces 1530E)
Tags: Greedy, strings

Prefix function of string $$$t = t_1 t_2 \ldots t_n$$$ and position $$$i$$$ in it is defined as the length $$$k$$$ of the longest proper (not equal to the whole substring) prefix of substring $$$t_1 t_2 \ldots t_i$$$ which is also a suffix of the same substring.For example, for string $$$t = $$$ abacaba the values of the prefix function in positions $$$1, 2, \ldots, 7$$$ are equal to $$$[0, 0, 1, 0, 1, 2, 3]$$$.Let $$$f(t)$$$ be equal to the maximum value of the prefix function of string $$$t$$$ over all its positions. For example, $$$f($$$abacaba$$$) = 3$$$.You are given a string $$$s$$$. Reorder its characters arbitrarily to get a string $$$t$$$ (the number of occurrences of any character in strings $$$s$$$ and $$$t$$$ must be equal). The value of $$$f(t)$$$ must be minimized. Out of all options to minimize $$$f(t)$$$, choose the one where string $$$t$$$ is the lexicographically smallest.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.The only line of each test case contains string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) consisting of lowercase English letters.It is guaranteed that the sum of lengths of $$$s$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print a single string $$$t$$$.The multisets of letters in strings $$$s$$$ and $$$t$$$ must be equal. The value of $$$f(t)$$$, the maximum of prefix functions in string $$$t$$$, must be as small as possible. String $$$t$$$ must be the lexicographically smallest string out of all strings satisfying the previous conditions.

Note: 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$$$.In the first test case, $$$f(t) = 0$$$ and the values of prefix function are $$$[0, 0, 0, 0, 0]$$$ for any permutation of letters. String ckpuv is the lexicographically smallest permutation of letters of string vkcup.In the second test case, $$$f(t) = 1$$$ and the values of prefix function are $$$[0, 1, 0, 1, 0, 1, 0]$$$.In the third test case, $$$f(t) = 5$$$ and the values of prefix function are $$$[0, 1, 2, 3, 4, 5]$$$.

Sample Inputs:
3
vkcup
abababa
zzzzzz

Sample Outputs:
ckpuv
aababab
zzzzzz

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 = list(readStr())
    n = len(s)
    cnt = [0] * 26
    s.sort()
    for i in range(n):
        cnt[ord(s[i]) - ord('a')] += 1
    nums = 0
    for i in range(26):
        if cnt[i] == 1:
            c = chr(ord('a') + i)
            s.remove(c)
            return c + ''.join(s)
        if cnt[i]:
            nums += 1
    v = cnt[ord(s[0]) - ord('a')]
    if v <= 2:
        return ''.join(s)
    elif 2 * v <= n + 2:
        ans = [s[0], s[0]]
        S = [i for i in range(n) if s[i] != s[0]]
        j = n
        if S:
            j = min(S)
            ans.append(s[j])
            j += 1
        v -= 2
        while v:
            ans.append(s[0])
            if j < n:
                ans.append(s[j])
                j += 1
            v -= 1
        if j < n:
            ans.append(''.join(s[j:]))
        return ''.join(ans)
    elif nums >= 3:
        j = k = -1
        for i in range(26):
            if cnt[i] == 0:
                continue
            if chr(i + ord('a')) == s[0]:
                continue
            if j == -1:
                j = i
            elif k == -1:
                k = i
                break
        (u, v) = (s.index(chr(j + ord('a'))), s.index(chr(k + ord('a'))))
        (s[1], s[u]) = (s[u], s[1])
        (s[u + 1], s[v]) = (s[v], s[u + 1])
        return ''.join(s)
    else:
        S = set(s)
        if len(S) == 1:
            return ''.join(s)
        else:
            (a, b) = list(S)
            if a > b:
                (a, b) = (b, a)
            return a + b * cnt[ord(b) - ord('a')] + a * (cnt[ord(a) - ord('a')] - 1)
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    s = input().strip()
    alpha = [0 for i in range(26)]
    n = len(s)
    an = ''
    sign = 0
    pp = s[0]
    ppp = 0
    for i in range(1, n):
        if pp != s[i]:
            ppp = 1
            break
    if ppp == 0:
        print(s)
        continue
    for i in range(n):
        alpha[ord(s[i]) - 97] += 1
    for i in range(26):
        if alpha[i] == 1:
            an += chr(i + 97)
            alpha[i] -= 1
            for j in range(26):
                an += chr(j + 97) * alpha[j]
            print(an)
            sign = 1
            break
        if sign == 1:
            break
    if sign == 1:
        continue
    an = ''
    for i in range(26):
        if alpha[i] != 0:
            if alpha[i] > n - alpha[i] + 2:
                e = 0
                for j in range(26):
                    if alpha[j] != 0:
                        e += 1
                if e == 2:
                    q = []
                    for j in range(26):
                        if alpha[j] != 0:
                            q.append(j)
                    an += chr(q[0] + 97)
                    alpha[q[0]] -= 1
                    an += chr(q[1] + 97) * alpha[q[1]]
                    an += chr(q[0] + 97) * alpha[q[0]]
                    break
                an += chr(i + 97)
                alpha[i] -= 1
                x = 0
                for j in range(i + 1, 26):
                    if alpha[j] != 0:
                        an += chr(j + 97)
                        alpha[j] -= 1
                        x = j
                        break
                an += chr(i + 97) * alpha[i]
                for j in range(x + 1, 26):
                    if alpha[j] != 0:
                        an += chr(j + 97)
                        alpha[j] -= 1
                        break
                q = ''
                for j in range(0, 26):
                    if j == i:
                        pass
                    else:
                        q += chr(j + 97) * alpha[j]
                an += q
                break
            q = ''
            for j in range(0, 26):
                if j == i:
                    pass
                else:
                    q += chr(j + 97) * alpha[j]
            l = len(q)
            sig = 0
            an += chr(i + 97)
            for j in range(alpha[i] - 1):
                if l == 0:
                    sig = 1
                if sig == 0:
                    an += chr(i + 97)
                    an += q[-l]
                    l -= 1
                    si = 0
                else:
                    an += chr(i + 97)
            if l != 0:
                an += q[-l:]
            break
    print(an)

Solution (Python):
from collections import Counter

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

def decompress(seq):
    for (a, cnt) in seq:
        for __ in range(cnt):
            yield a

def solve(s):
    c = Counter(s)
    if len(c) == 1:
        return s
    (ca, a) = min(((ca, a) for (a, ca) in c.items()))
    if ca == 1:
        t = a
        c.pop(a)
        for (a, ca) in sorted(c.items()):
            t += a * ca
        return t
    q = sorted(c.items())
    (a, ca) = q[0]
    assert ca >= 2
    if ca <= len(s) // 2 + 1:
        t = a * 2
        ca -= 2
        other = decompress(q[1:])
        while ca:
            t += next(other) + a
            ca -= 1
        return t + ''.join(other)
    if len(q) == 2:
        (b, knt) = q[1]
        return a + b * knt + a * (ca - 1)
    assert len(q) >= 3
    (b, cb) = q[1]
    (c, cc) = q[2]
    t = a + b + a * (ca - 1) + c + b * (cb - 1) + c * (cc - 1)
    return t + ''.join(decompress(q[3:]))

def test_solve():
    assert solve('aaa') == 'aaa'
    assert solve('aaabb') == 'aabab'
    assert solve('aaaabb') == 'aababa'
    assert solve('aaaaabb') == 'abbaaaa'
    assert solve('aaaaabc') == 'baaaaac'
    assert solve('aaaaaaabbcc') == 'abaaaaaacbc'
    assert solve('aaaaaaaaabbccdd') == 'abaaaaaaaacbcdd'

def main():
    t = int(input())
    for __ in range(t):
        print(solve(input()))
if __name__ == '__main__':
    main()