Chương trình tìm số lần thay đổi tối thiểu để chuỗi có K ký tự riêng biệt trong Python

Cho chuỗi chữ thường và số . Tìm số lần thay đổi ký tự tối thiểu để chuỗi kết quả có tối đa ký tự riêng biệt.

Ví dụ: , → kết quả 1 (bỏ 'w' để còn x, y, z).

Giải thuật (Đếm tần suất + Sắp xếp)

1. Đếm tần suất từng ký tự → .
2. Sắp xếp các tần suất tăng dần → .
3. Cần loại bỏ ký tự ít xuất hiện nhất.
4. Tổng tần suất của các ký tự đó là đáp án.

Ví dụ minh họa

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

Đầu vào

"wxxyyzzxx", 3

Đầu ra

1