โปรแกรมนับการลบน้อยที่สุดเพื่อทำให้ความถี่ตัวอักษรไม่ซ้ำกันใน Python

ปัญหา

สตริง s "ดี" ถ้าไม่มีตัวอักษร 2 ตัวที่มีความถี่เท่ากัน หาจำนวนการลบตัวอักษรน้อยที่สุดทำให้ดี

ตัวอย่าง

s="ssstttuu" → ผลลัพธ์ 2 (ลบ t หนึ่งตัว → 3s,2t,2u แล้วลบ t หรือ u อีกตัว)

ขั้นตอนการแก้ปัญหา

1. val := Counter(s), res := 0
2. numlist := sorted(val.values())
3. วน i 0 ถึง len(numlist)-2:
   • ถ้า numlist[i] > 0 and numlist[i] == numlist[i+1]:
     • numlist[i] -= 1; res += 1
     • k := i-1, m := i
     • بينما numlist[m] > 0 and numlist[m] == numlist[k]:
       • numlist[k] -= 1; k -= 1; m -= 1; res += 1
4. คืน res

การนำไปใช้งาน (Python)

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