Longest Palindrome trong C++

Cho chuỗi s (chữ hoa/thường phân biệt), tìm độ dài palindrome dài nhất có thể xây dựng từ các ký tự của s.

Ví dụ: "abccccdd" → "dccaccd" độ dài 7.

Giải thuật

1. Đếm tần suất từng ký tự.
2. Tổng độ dài = tổng các tần suất chẵn + (tần suất lẻ - 1) cho mỗi ký tự lẻ + (có ký tự lẻ ? 1 : 0).

Ví dụ triển khai C++

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

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char, int> freq;
        for (char c : s) ++freq[c];
        
        int len = 0;
        bool hasOdd = false;
        for (auto& [c, cnt] : freq) {
            if (cnt % 2 == 0) len += cnt;
            else { len += cnt - 1; hasOdd = true; }
        }
        return len + (hasOdd ? 1 : 0);
    }
};

int main() {
    Solution ob;
    cout << ob.longestPalindrome("abccccdd"); // 7
    return 0;
}

Đầu vào / Đầu ra

Input: "abccccdd"
Output: 7