การสร้างสตริงพาลินโดรม K ตัวใน C++

ข้อสังเกตสำคัญ

ถ้ามีตัวอักษรที่ความถี่เป็นเลขคี่ทั้งหมด odd ตัว แล้วเราต้องการสร้าง k พาลินโดรม → ต้องมี odd <= k เพราะแต่ละพาลินโดรมรับตัวอักษรคี่ได้สูงสุด 1 ตัว

แนวทางแก้ปัญหา

1. ถ้า n = s.length() < k → false (ตัวอักษรไม่พอให้แต่ละสตริงมีอย่างน้อย 1 ตัว)
2. ถ้า n == k → true (แต่ละตัวอักษรเป็นสตริงเดี่ยว ซึ่งเป็นพาลินโดรม)
3. นับความถี่ตัวอักษรแต่ละตัว (ใช้ map/array)
4. นับจำนวนตัวอักษรที่มีความถี่คี่ → odd
5. คืนค่า odd <= k

ตัวอย่างโค้ด 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& [ch, cnt] : freq)
            if (cnt % 2 == 1) odd++;

        return odd <= k;
    }
};

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

ตัวอย่างการทำงาน

s = "true", k = 4

• ความถี่: t:1, r:1, u:1, e:1 → odd = 4
• odd (4) <= k (4) → true
• จัดเป็น: "t", "r", "u", "e" (ทุกตัวเป็นพาลินโดรม)

ความซับซ้อน

• เวลา: O(n) – วนลูปนับความถี่ครั้งเดียว
• พื้นที่: O(1) – ตัวอักษร high 26 ตัว (lowercase) หรือ 52 ตัว (รวม uppercase)

ข้อสังเกตเพิ่มเติม

• ไม่จำเป็นต้องสร้างพาลินโดรมจริง – ตรวจสอบเงื่อนไขเพียงพอแล้ว
• กรณี k > n จัดการได้ที่เงื่อนไขแรก
• ใช้ unordered_map เร็วกว่า map สำหรับการนับความถี่