# **Palindrome Reorder**
**Bài toán**: Cho một xâu, nhiệm vụ của bạn là sắp xếp lại các ký tự của nó sao cho xâu đó trở thành một xâu đối xứng *(xâu đối xứng là xâu khi đọc xuôi hoặc ngược đều như nhau)*.

***Input:***
* Một dòng duy nhất gồm một xâu có độ dài $n$ chỉ có các ký tự chữ cái in hoa A - Z.

***Ràng buộc:***
* $1 ≤ n ≤ 10^6$

***Output:***
* In ra một xâu đối xứng chứa các kí tự của xâu ban đầu. Bạn có thể in ra bất kỳ đáp án thỏa mãn nào. Nếu không có đáp án, in *NO SOLUTION*.

***Sample input:***

AAAACACBA

***Sample output:***

AACABACAA

## Ý tưởng
**Bước 1:**
Khởi tạo một mảng để đếm tần suất xuất hiện của mỗi ký tự trong xâu. Đồng thời kiểm tra xem có bao nhiêu ký tự bị lẻ, ví dụ $s$ = $AA$<span style="color:red">$AB$</span> thì ta thấy rằng có 1 ký tự $A$ và $B$ bị lẻ. Khởi tạo hai biến $even$ và $odd$ lần lượt là các biến lưu số lượng ký tự *không lẻ* và ký tự *lẻ*.

**Bước 2:**
Kiểm tra xem với lượng ký tự đó thì ta có thể sắp xếp lại thành 1 xâu đối xứng được hay không.
* Nếu xâu có độ dài là *chẵn* thì không được có bất kỳ 1 ký tự lẻ nào.
* Nếu xâu có độ dài là *lẻ* thì không được có nhiều hơn 1 ký tự lẻ.

**Bước 3:**
Khởi tạo ba biến $l$, $r$, $m$ để lưu kết quả. Trong trường hợp xâu có độ dài *chẵn* thì ta chỉ cần $l$ và $r$, còn xâu có độ dài *lẻ* thì ta cần cả ba. Mỗi lần duyệt qua được số lượng ký tự không lẻ thì ra thêm lần lượt chúng vào $l$ và $r$ đồng thời -2 số lượng đã đếm, khi số lượng đếm của ký tự đó = 0 nghĩa là ta đã xử lí xong ký tự đó và có thể tiếp tục xử lí những ký tự khác. Còn ký tự bị lẻ ta sẽ xử lí sau cùng.

Giả sử ta có xâu $s$ = "$CBBAA$" thì khi chạy xong ý tưởng trên, nó sẽ in ra $ABCAB$ ($l$ = $AB$, $m$ = $C$, $r$ = $AB$) trong khi đáp án ta cần tìm là $ABCBA$. Chính vì thế nên ta sẽ cần đảo lại xâu $r$ bằng cách sử dụng hàm $reverse()$ trong thư viện *<algorithm>*.

## Code mẫu:

// author : hatakaze (a.k.a Tran Gia Huy)
#include "bits/stdc++.h"
using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define int long long

int cnt[26] = {0};
void solve() {
    string s; cin >> s;
    bool ok = false;
    int even = 0, odd = 0;
    for(int i = 0; i < sz(s); i++) {
        ++cnt[s[i] - 'A'];
    }
    for(int i = 0; i < 26; i++) {
        if(cnt[i] != 0) {
            if(cnt[i] % 2 == 0) ++even;
            else ++odd;
        }
    }
    if(odd != 0 && sz(s) % 2 == 0) {
        cout << "NO SOLUTION";
        return;
    }
    if(odd > 1 && sz(s) % 2 == 1) {
        cout << "NO SOLUTION";
        return;
    }
    string l, r, m;
    for(int i = 0; i < 26; i++) {
        if(cnt[i] != 0){
            while(cnt[i] > 1) {
                l += char(i + 'A');
                r += char(i + 'A');
                cnt[i] -= 2;
            }
        }
    }
    for(int i = 0; i < 26; i++) {
        if(cnt[i] == 1) {
            m += char(i + 'A');
            ok = true;
            break;
        }
    }
    reverse(all(r));
    if(ok) {
        cout << l << m << r;
        return;
    }
    cout << l << r;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}

## Giải thích:

**Dòng 15:**
Ta gọi các số từ 0 đến 25 là các số đại diện cho các ký tự từ A - Z (VD: *A = 0*, *B = 1*, *C = 2*,...). Mà theo mã ASCII thì số 65 đến 90 tương ứng các ký tự A - Z nên ta chỉ cần trừ cho 'A' hoặc 65 để ra được các số trong khoảng 0 đến 25 cho dễ làm.

**Dòng 34 đến 37:**
Ta chỉ thêm các ký tự vào $l$ và $r$ khi và chỉ khi tần suất xuất hiện của nó lớn hơn 1. Ví dụ, ký tự A xuất hiện 3 lần thì ta thêm 1 ký tự A vào $l$ và 1 ký tự A vào $r$ đồng thời trừ đi 2 (nghĩa là đã xử lí xong 2 ký tự). Khi đó thì ta còn lại lẻ 1 ký tự thì ta sẽ xử lí nó sau cùng.

**Bài tập tham khảo:**
* https://cses.fi/problemset/task/1755
* https://lqdoj.edu.vn/problem/cses1755