Chương trình đếm số lần xóa tối thiểu để tần suất ký tự duy nhất trong Python

Chuỗi s gọi là tốt nếu không có 2 ký tự khác nhau cùng tần suất. Tìm số xóa ít nhất để s tốt.

Ví dụ: s="ssstttuu" → 2. Xóa 1 't' → tần suất: s=3, t=2, u=2. Xóa thêm 1 't' hoặc 'u' → tốt.

Giải thuật (Sắp xếp tần suất + điều chỉnh)

1. Đếm tần suất, sắp xếp mảng numlist tăng dần.
2. Duyệt i từ 0 đến len-2:
   • Nếu numlist[i] > 0 và numlist[i] == numlist[i+1]:
     • Giảm numlist[i]--, res++.
     • Lùi về trước (k=i-1, m=i) để sửa các xung đột do giảm: trong khi numlist[m] == numlist[k] > 0: numlist[k]--, k--, m--, res++.
3. Trả về res.

Ví dụ minh họa

from collections import Counter

def solve(s):
    val = Counter(s)
    res = 0
    numlist = sorted(val.values())
    for i in range(len(numlist) - 1):
        if numlist[i] and numlist[i] == numlist[i+1]:
            numlist[i] -= 1
            res += 1
            k, m = i - 1, i
            while numlist[m] and numlist[m] == numlist[k]:
                numlist[k] -= 1
                k -= 1
                m -= 1
                res += 1
    return res

s = "ssstttuu"
print(solve(s))

Đầu vào

"ssstttuu"

Đầu ra

2