สมมติว่าเรามีสตริง s ของอักขระอักษรตัวพิมพ์เล็ก และอีกจำนวนหนึ่งคือ k เราต้องหาจำนวนขั้นต่ำของการเปลี่ยนแปลงที่จำเป็นในสตริง เพื่อให้สตริงที่ได้มีอักขระที่แตกต่างกันมากที่สุด k ตัว ในกรณีนี้ การเปลี่ยนแปลงจริง ๆ แล้วเป็นการเปลี่ยนอักขระตัวเดียวเป็นอักขระอื่น
ดังนั้น หากอินพุตเป็น s ="wxxyyzzxx", k =3 เอาต์พุตจะเป็น 1 เนื่องจากเราสามารถลบตัวอักษร "w" ออกเพื่อให้ได้อักขระที่แตกต่างกัน 3 ตัว (x, y และ z)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
count :=แผนที่ของตัวละครแต่ละตัวใน s และความถี่
-
sv :=รายการเรียงลำดับของค่าความถี่
-
ตอบ :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง (ขนาดของการนับ) - k - 1 ทำ
-
ans :=ans + sv[i]
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
"wxxyyzzxx",3
ผลลัพธ์
1
