Gọi ~cnt_c~ là số lần xuất hiện của ký tự ~c~ trong xâu ~s~. Dễ thấy, một xâu là đối xứng nếu có không quá một ký tự ~c~ với ~cnt_c~ lẻ.

Ký hiệu các ký tự có ~cnt_c~ lẻ trong xâu ~s~ ban đầu là ~a_1, a_2, ..., a_k~ (được sắp xếp theo thứ tự xuất hiện bảng chữ cái). Thay thế bất kỳ một trong các ký tự ~a_k~ bằng ~a_1~, ~a_{k - 1}~ bằng ~a_2~ và cứ tiếp tục như vậy cho đến giữa dãy ~a~.

Sau quá trình này, xâu ~s~ sẽ không còn nhiều hơn một ký tự ~c~ có ~cnt_c~ lẻ . Khi đó, duyệt ~c~ từ a đến z, nếu có một chữ cái ~c~ với ~cnt_c~ lẻ, thì ký tự nằm ở giữa xâu ~s~ sẽ là ~c~. Nửa đầu của xâu cần tìm sẽ chứa ~\frac{cnt_c}{2}~ lần xuất hiện của ký tự ~c~ (~c~ được duyệt theo thứ tự xuất hiện trong bảng chữ cái để đảm bảo thứ tự từ điển của xâu tìm được là nhỏ nhất). Nửa sau là đảo ngược của nửa đầu xâu ~s~.

Ví dụ đối với xâu ~s =~ aabcd, ban đầu chúng ta sẽ thay thế d bằng b. Sau đó, chúng ta sẽ hoán vị các kí tự trong xâu để nhận được xâu ~s=~abcba. Dễ dàng nhận thấy, đó là đáp án tối ưu.

Độ phức tạp: ~O(n)~

Code tham khảo

#include <bits/stdc++.h>

using namespace std;
string s;
int cnt[26];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    for(int i = 0; i < (int)s.size(); ++i)
        cnt[s[i] - 'a']++;
    int i = 0, j = 25;
    while(i < j)
    {
        while(i < j && cnt[i] % 2 == 0)  ++i;
        while(i < j && cnt[j] % 2 == 0)  --j;
        cnt[i]++, cnt[j]--;
    }
    int l = 0, r = (int)s.size() - 1;
    for(int i = 0; i <= 25; ++i)
    {
        while(cnt[i] >= 2)
        {
            s[l++] = s[r--] = char(i + 'a');
            cnt[i] -= 2;
        }
        if(cnt[i] > 0)
        {
            s[s.size() / 2] = char(i + 'a');
            --cnt[i];
        }
    }
    cout << s;
    return 0;
}