Minimax
Contest: Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Difficulty rating: 2100
Tags: constructive algorithms, 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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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]$$$.

Example input:
3
vkcup
abababa
zzzzzz

Example output:
ckpuv
aababab
zzzzzz

Editorial:
This problem required careful case analysis.
First of all, if all characters of $$$s$$$ are the same, there is nothing to reorder: $$$t = s$$$, and $$$f(t) = |t| - 1$$$.
Second, if the first character of $$$t$$$ appears somewhere else in the string, $$$f(t) \ge 1$$$. Otherwise, $$$f(t) = 0$$$.
Thus, if some character has only one occurrence in $$$s$$$, choose the smallest such character and put it at the front of $$$t$$$, followed by all the remaining characters of $$$s$$$ in alphabetical order. That's the lexicographically smallest way to obtain $$$f(t) = 0$$$.
Otherwise, if all characters have at least two occurrences in $$$s$$$, we can always reach $$$f(t) = 1$$$. The easiest way to construct such $$$t$$$ is to choose any character, put one of its occurrences at the front of $$$t$$$, put the remaining occurrences at the back of $$$t$$$, and put the rest of the characters in-between ordered arbitrarily. However, we have to minimize $$$t$$$ lexicographically.
First, we have to put the smallest character of $$$s$$$ at the front of $$$t$$$, say, a. Then, let's try to follow it with the same character. In this case, $$$t$$$ starts with aa, and we can't have another occurrence of aa anywhere in $$$t$$$, as we aim at $$$f(t) = 1$$$, which means that at most half of the letters (approximately) can be equal to a. The exact condition of whether we can start with aa is: the number of occurrences of a in $$$s$$$ must not exceed $$$\frac{|s|}{2} + 1$$$. If this is the case, the lexicographically smallest $$$t$$$ we can form will look like aabababacacadddeeefffff.
If $$$t$$$ starts with a, but can not start with aa, let's find the second smallest character in $$$s$$$, say, b, and start $$$t$$$ with ab. Now we are not allowed to have ab anywhere else in $$$t$$$. There are two (final) cases:
• if $$$s$$$ doesn't have any other characters except a and b, we have to put all the remaining b's in front of all a's. The smallest $$$t$$$ will look like abbbbbbbaaaaaaaaaaaaa.
• otherwise, find the third smallest character in $$$s$$$, say, c. We can now afford putting all a's after the ab prefix if we follow these a's with c. The smallest $$$t$$$ will look like abaaaaaaaaaaacbbbcddd.
It's possible to consider less cases if you implement a function that checks if a prefix of $$$t$$$ can be finished with the remaining characters of $$$s$$$ to obtain $$$f(t) = 1$$$. Then $$$t$$$ can be formed character-by-character from left to right. This approach still requires care, though.