Xây dựng K chuỗi palindrome trong C++

Giới thiệu

Cho chuỗi s và số nguyên k. Hỏi có thể dùng tất cả ký tự của s để xây dựng k chuỗi palindrome (đối xứng) không rỗng hay không.

Quan sát quan trọng

• Mỗi chuỗi palindrome có thể chứa tối đa 1 ký tự xuất hiện số lẻ lần (ở giữa).
• Do đó, số lượng ký tự xuất hiện số lẻ lần trong s phải ≤ k.
• Ngoài ra, cần |s| ≥ k (mỗi chuỗi ít nhất 1 ký tự).

Thuật toán

1. Nếu n < k → false.
2. Nếu n == k → true (mỗi ký tự thành 1 chuỗi).
3. Đếm tần suất mỗi ký tự.
4. Đếm số ký tự có tần suất lẻ (odd).
5. Trả về odd ≤ k.

Cài đặt C++

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

class Solution {
public:
    bool canConstruct(string s, int k) {
        int n = s.size();
        if (n < k) return false;
        if (n == k) return true;
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        int odd = 0;
        for (auto& p : freq) odd += (p.second & 1);
        return odd <= k;
    }
};

int main() {
    Solution ob;
    cout << ob.canConstruct("true", 4); // Output: 1 (true)
    return 0;
}

Ví dụ

s = "true", k = 4. Tần suất: t:1, r:1, u:1, e:1 → odd = 4 ≤ 4 → true. Các chuỗi: "t", "r", "u", "e".

Độ phức tạp

• Thời gian: O(n) – duyệt chuỗi và map.
• Không gian: O(1) – map tối đa 26/52/256 ký tự.