Given a string $s$, the goal is to find a permutation $t$ such that the maximum value of the border length $f(i)$ across all prefixes $i$ of $t$ is minimized. Among all permutations that achieve this minimum, $t$ must be the lexicographically smallest.

Character Analysis and Minimum Border Criteria

For any string containing at least two distinct characters, it is always possible to achieve a maximum prefix border of either 0 or 1. Let $st$ be the lexicographically smallest character present, $se$ the second smallest, and $th$ the third smallest. Let $cnt[c]$ denote the frequency of character $c$, and $K$ be the total number of unique characters.

Case 1: Achieving a Maximum Border of 0

A maximum border of 0 is achievable if and only if there exists at least one character with a frequency of exactly 1. To maintain lexicographical order, we find the smallest character $c$ such that $cnt[c] = 1$. We place this character at the beginning and then append all remaining characters in ascending alphabetical order.

int targetChar = -1;
for (int i = 0; i < 26; ++i) {
    if (charFreq[i] == 1) {
        targetChar = i;
        break;
    }
}

if (targetChar != -1) {
    cout << (char)('a' + targetChar);
    charFreq[targetChar]--;
    for (int i = 0; i < 26; ++i) {
        while (charFreq[i]--) cout << (char)('a' + i);
    }
    cout << endl;
    return;
}

Case 2: Single Unique Character

If the string consists of only one type of character ($K=1$), the permutation is fixed. The maximum border will be $n-1$.

if (uniqueCount == 1) {
    cout << s << endl;
    return;
}

Case 3: Achieving a Maximum Border of 1

When no character has a frequency of 1, we aim for a maximum border of 1. We prioritize starting the string with the smallest character $st$.

Subcase: Starting with two $st$ characters

We can start with $st, st$ if there are enough other characters to seperate the remaining $st$ characters so that no prefix $st \dots st$ matches a suffix. Specifically, if $cnt[st] - 2 \le (n - cnt[st])$, we can alternate $st$ with other characters.

if (charFreq[st] - 2 <= (totalLen - charFreq[st])) {
    cout << (char)('a' + st) << (char)('a' + st);
    charFreq[st] -= 2;
    for (int i = st + 1; i < 26; ++i) {
        while (charFreq[i] > 0) {
            if (charFreq[st] > 0) {
                cout << (char)('a' + i) << (char)('a' + st);
                charFreq[i]--;
                charFreq[st]--;
            } else {
                cout << (char)('a' + i);
                charFreq[i]--;
            }
        }
    }
    cout << endl;
}

Subcase: Starting with $st, se$

If the condition $cnt[st] - 2 \le (n - cnt[st])$ fails, we cannot start with $st, st$. Enstead, we start with $st, se$. The arrangement of the remaining characters depends on the number of unique characters.

1. If $K \ge 3$: To keep the string lexicographically small, we place all remaining $st$ characters after the first $se$, then use the third character $th$ to break any potential border, followed by the rest of the characters in order. Pattern: $st, se, [all\ remaining\ st], th, [rest]$

2. If $K = 2$: We must place all $se$ characters after the first $st$, followed by all remaining $st$ characters. Pattern: $st, [all\ se], [all\ remaining\ st]$

else {
    cout << (char)('a' + st);
    charFreq[st]--;
    if (uniqueCount >= 3) {
        cout << (char)('a' + se);
        charFreq[se]--;
        while (charFreq[st]--) cout << (char)('a' + st);
        cout << (char)('a' + th);
        charFreq[th]--;
    } else {
        while (charFreq[se]--) cout << (char)('a' + se);
    }
    for (int i = 0; i < 26; ++i) {
        while (charFreq[i] > 0 && charFreq[i]--) cout << (char)('a' + i);
    }
    cout << endl;
}

Implementation Logic

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void process() {
    string s;
    cin >> s;
    int n = s.length();
    vector<int> freq(26, 0);
    for (char c : s) freq[c - 'a']++;

    int unique = 0;
    for (int i = 0; i < 26; i++) if (freq[i] > 0) unique++;

    if (unique == 1) {
        cout << s << "\n";
        return;
    }

    for (int i = 0; i < 26; i++) {
        if (freq[i] == 1) {
            cout << (char)('a' + i);
            freq[i]--;
            for (int j = 0; j < 26; j++) {
                while (freq[j]--) cout << (char)('a' + j);
            }
            cout << "\n";
            return;
        }
    }

    int st = -1, se = -1, th = -1;
    for (int i = 0; i < 26; i++) {
        if (freq[i] > 0) {
            if (st == -1) st = i;
            else if (se == -1) se = i;
            else if (th == -1) th = i;
        }
    }

    if (freq[st] - 2 <= n - freq[st]) {
        cout << (char)('a' + st) << (char)('a' + st);
        freq[st] -= 2;
        for (int i = st + 1; i < 26; i++) {
            while (freq[i]--) {
                cout << (char)('a' + i);
                if (freq[st] > 0) {
                    cout << (char)('a' + st);
                    freq[st]--;
                }
            }
        }
        cout << "\n";
    } else if (unique >= 3) {
        cout << (char)('a' + st) << (char)('a' + se);
        freq[st]--; freq[se]--;
        while (freq[st]--) cout << (char)('a' + st);
        cout << (char)('a' + th);
        freq[th]--;
        for (int i = 0; i < 26; i++) {
            while (freq[i] > 0 && freq[i]--) cout << (char)('a' + i);
        }
        cout << "\n";
    } else {
        cout << (char)('a' + st);
        freq[st]--;
        while (freq[se]--) cout << (char)('a' + se);
        while (freq[st]--) cout << (char)('a' + st);
        cout << "\n";
    }
}

int main() {
    int t; 
    cin >> t;
    while (t--) process();
    return 0;
}