โปรแกรมนับจำนวนการลบขั้นต่ำที่จำเป็นในการทำให้ความถี่อักขระไม่ซ้ำกันใน Python

สมมติว่าเรามีสตริง s s เรียกว่า ดี หากไม่มีอักขระสองตัวใน s ที่มีความถี่เท่ากัน เราต้องหาจำนวนอักขระขั้นต่ำที่เราจำเป็นต้องลบเพื่อสร้างสตริงที่ดี

ดังนั้น หากอินพุตเป็น s ="ssstttuu" ผลลัพธ์จะเป็น 2 เพราะหากเราลบ 't' หนึ่งตัว จะมีสาม 's' สอง 't' และสอง 'u' แล้วจึงลบอีกครั้ง อย่างใดอย่างหนึ่ง 't' หรือ 'u' เพื่อให้ดี

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• val :=แผนที่ใหม่ที่มีความถี่ของอักขระแต่ละตัวของ s
• res :=0
• numlist :=เรียงลำดับรายการค่าความถี่ทั้งหมดจาก val
• สำหรับฉันในช่วง 0 ถึงขนาดของ numlist -2 ทำ
  • ถ้า numlist[i] ไม่ใช่ศูนย์และ numlist[i] เหมือนกับ numlist[i+1] แล้ว
    • numlist[i] :=numlist[i] - 1
    • res :=res + 1
    • k :=i-1
    • ม :=ผม
    • ในขณะที่ numlist[m] ไม่เป็นศูนย์ และ numlist[m] เหมือนกับ numlist[k], do
      • numlist[k] :=numlist[k] - 1
      • k :=k - 1
      • ม :=ม. - 1
      • res :=res + 1
• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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))

อินพุต

"ssstttuu"

ผลลัพธ์

2