\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-forces>}}\)

• Thử xóa từng dãy kí tự và kiểm tra phần còn lại có thỏa không

\(\color{orange}{\text{Hint 2 <Implementation>}}\)

• Ta có nhận xét như sau

Với mỗi kí tự xuất hiện \(2 \times f + r\) lần với \(r \in [0, 1]\)

Ta có thể chia \(n\) kí tự qua trái và \(n\) kí tự tương ứng qua phải

Còn lại là một kí tự lẻ bắt buộc phải ở trung tâm khi \(r = 1\)

Vậy thì nếu có kí tự lẻ khác cạnh hàng, mình sẽ xóa các kí tự lẻ đó, chỉ để lại 1 hoặc 0 cái cuối cùng

Gọi số số lẻ là \(cnt\) thì

Đáp án là \(res = cnt - 1\) khi \(cnt > 0\)

Đáp án là \(res = cnt = 0\) khi \(cnt = 0\)

\(\color{green}{\text{Preference AC Code }}\): Implementation

\(^{^{\color{purple}{\text{Complexity : }} O(|s| + alphabet)\ \color{purple}{\text{time}}\ ||\ O(|s| + alphabet)\ \color{purple}{\text{memory}}}}\)

int main()
{
    string s;
    cin >> s;

    vector<int> fre(256, 0);
    for (char c : s) fre[c]++;

    int res = 0;
    for (int x : fre) res += (x % 2 == 1);
    cout << res - (res > 0);
    return 0;
}