โปรแกรมหาจำนวนการเปลี่ยนแปลงน้อยที่สุดเพื่อให้สตริงมีตัวอักษรไม่เกิน K ชนิดใน Python

สมมติว่าเรามีสตริง s ตัวพิมพ์เล็ก และตัวเลข k เราต้องหาจำนวนการเปลี่ยนแปลงน้อยที่สุด (เปลี่ยนตัวอักษรหนึ่งตัวเป็นอีกตัวหนึ่ง) เพื่อให้สตริงที่ได้มีตัวอักษรที่แตกต่างกันไม่เกิน k ชนิด

ตัวอย่างเช่น s = "wxxyyzzxx", k = 3 ผลลัพธ์คือ 1 (ลบ 'w' ทิ้งเหลือ x, y, z 3 ชนิด)

ขั้นตอนการแก้ปัญหา (Greedy + Frequency Count)

1. นับความถี่แต่ละตัวอักษรใน s ด้วย Counter
2. เรียงค่าความถี่จากน้อยไปมาก sv = sorted(count.values())
3. ans = 0
4. วนลูป i จาก 0 ถึง len(count) - k - 1 (จำนวนตัวอักษรที่ต้องลบ):
   • ans += sv[i] (ลบตัวอักษรที่มีความถี่น้อยที่สุดก่อน)
5. คืนค่า ans

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

from collections import Counter

class Solution:
    def solve(self, s, k):
        count = Counter(s)
        sv = sorted(count.values())
        ans = 0
        
        for i in range(len(count) - k):
            ans += sv[i]
        
        return ans

ob = Solution()
s = "wxxyyzzxx"
k = 3
print(ob.solve(s, k))  # Output: 1

อินพุต

"wxxyyzzxx", 3

เอาต์พุต

1