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

Giả sử chúng ta có một chuỗi s, s được cho là tốt nếu không có hai ký tự khác nhau trong s có cùng tần số. Chúng tôi phải tìm số ký tự tối thiểu mà chúng tôi cần xóa để tạo thành một chuỗi tốt.

Vì vậy, nếu đầu vào là s =​​"ssstttuu", thì đầu ra sẽ là 2 vì nếu chúng ta xóa một 't', thì sẽ có ba 's', hai 't' và hai 'u', sau đó lại xóa một, hoặc 't' hoặc 'u', để làm cho chúng tốt.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• val:=một bản đồ mới chứa tần số của mỗi ký tự trong s
• res:=0
• numlist:=sắp xếp danh sách tất cả các giá trị tần suất từ ​​val
• đối với tôi trong phạm vi 0 đến kích thước của numlist -2, thực hiện
  • nếu numlist [i] khác 0 và numlist [i] giống numlist [i + 1], thì
    • numlist [i]:=numlist [i] - 1
    • res:=res + 1
    • k:=i-1
    • m:=i
    • trong khi numlist [m] khác 0 và numlist [m] giống numlist [k], hãy thực hiện
      • numlist [k]:=numlist [k] - 1
      • k:=k - 1
      • m:=m - 1
      • res:=res + 1
• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

from collections import Counter
def solve(s):
   val = Counter(s)
   res = 0
   numlist = sorted([i for i in val.values()])
   for i in range(len(numlist)-1):
      if numlist[i] and numlist[i] == numlist[i+1]:
         numlist[i] -= 1
         res += 1
         k = i-1
         m = 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