Chuỗi con độ dài chẵn lớn nhất là hoán vị của palindrome trong C++

Đề bài

Cho một chuỗi, tìm độ dài lớn nhất của chuỗi con có thể sắp xếp thành palindrome.

Ví dụ

Nếu chuỗi = "5432112356" thì kết quả = 6 vì palindrome dài nhất là "321123" độ dài 6.

Thuật toán

• Chuỗi con độ dài lẻ không được xem xét
• Chuỗi con độ dài chẵn có thể là lời giải nếu mọi ký tự xuất hiện số lần chẵn (kiểm tra bằng bảng đếm)
• Mở rộng chuỗi con bằng cách thêm ký tự tiếp theo và kiểm tra đệ quy

Chương trình C++

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

unordered_map<int, int> countt;

bool isPalindromePossible(unordered_map<int, int> &countt) {
    for (auto key : countt) {
        if (key.second & 1)
            return false;
    }
    return true;
}

int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) {
    if (end == str.length()) {
        if ((end - start) % 2 == 0 && isPalindromePossible(countt))
            return end - start;
        return 0;
    } else {
        if ((end - start) % 2 == 0) {
            if (isPalindromePossible(countt)) {
                countt[str[end]]++;
                return max(end - start, getMaxPalindrome(str, countt, start, end + 1));
            } else {
                countt[str[end]]++;
                return getMaxPalindrome(str, countt, start, end + 1);
            }
        } else {
            countt[str[end]]++;
            unordered_map<int, int> c(countt.begin(), countt.end());
            int length = getMaxPalindrome(str, c, start, end + 1);
            countt[str[end]]--;
            countt[str[start]]--;
            return max(length, getMaxPalindrome(str, countt, start + 1, end));
        }
    }
}

int main() {
    string str = "5432112356";
    int start = 0, end = 0;
    cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl;
    return 0;
}

Kết quả

Maximum palindrome length = 6

Lưu ý

Thuật toán đệ quy này có độ phức tạp cao. Có thể tối ưu bằng kỹ thuật cửa sổ trượt với bitmask (vì chỉ 10 chữ số 0-9) đạt O(n).