ตรวจสอบว่าสร้าง Palindrome K ตัวจากตัวอักษรสตริงได้หรือไม่ใน Python

กำหนดสตริง s และตัวเลข k ตรวจสอบว่าสามารถสร้าง palindrome k ตัวใช้ตัวอักษรทั้งหมดใน s ได้หรือไม่

ตัวอย่าง: s = "amledavmel", k = 2 → True (ทำได้ "level" และ "madam")

หลักการ

Palindrome แต่ละตัวต้องมีตัวอักษรคี่ได้สูงสุด 1 ตัว ดังนั้น จำนวนตัวอักษรที่มีความถี่คี่ ต้อง ≤ k

ขั้นตอน

1. นับความถี่ตัวอักษรด้วย Counter
2. นับจำนวนตัวอักษรที่มีความถี่คี่ (cnt)
3. หาก cnt > k คืน False มิฉะนั้น True

ตัวอย่างโค้ด

from collections import Counter

class Solution:
    def solve(self, s, k):
        d = Counter(s)
        cnt = 0
        for key in d:
            if d[key] & 1:
                cnt += 1
            if cnt > k:
                return False
        return True

ob = Solution()
s = "amledavmel"
k = 2
print(ob.solve(s, k))  # True

อินพุต

"amledavmel", 2

เอาต์พุต

True