Số lần xóa tối thiểu để hoán vị palindrome trong C++

Đề bài

Cho chuỗi S, cần tìm số ký tự tối thiểu có thể xóa để bất kỳ hoán vị nào của chuỗi S trở thành palindrome.

Ví dụ

Nếu str = "abcdba" thì xóa 1 ký tự là 'c' hoặc 'd'.

Thuật toán

1. Có 2 loại palindrome: độ dài chẵn và lẻ.
2. Palindrome độ dài chẵn phải có mọi ký tự xuất hiện số lần chẵn.
3. Palindrome độ dài lẻ phải có mọi ký tự xuất hiện số lần chẵn trừ một ký tự xuất hiện số lần lẻ.
4. Kiểm tra tần suất mỗi ký tự, những ký tự xuất hiện số lần lẻ được đếm. Kết quả là tổng số ký tự tần suất lẻ trừ 1.

Ví dụ mã C++

#include <bits/stdc++.h>
#define MAX 26
using namespace std;

int minCharactersRemoved(string str) {
    int hash[MAX] = {0};
    for (int i = 0; str[i]; ++i) {
        hash[str[i] - 'a']++;
    }
    int cnt = 0;
    for (int i = 0; i < MAX; ++i) {
        if (hash[i] & 1) {
            ++cnt;
        }
    }
    return (cnt == 0) ? 0 : (cnt - 1);
}

int main(){
    string str = "abcdba";
    cout << "Số ký tự cần xóa tối thiểu = " << minCharactersRemoved(str) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số ký tự cần xóa tối thiểu = 1