Python में वर्ण आवृत्ति को अद्वितीय बनाने के लिए न्यूनतम डिलीशन गिनने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s है, s को अच्छा कहा जाता है यदि s में कोई दो अलग-अलग वर्ण नहीं हैं जिनकी आवृत्ति समान हो। हमें s को एक अच्छी स्ट्रिंग बनाने के लिए हटाने के लिए आवश्यक वर्णों की न्यूनतम संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है s = "ssstttuu", तो आउटपुट 2 होगा क्योंकि यदि हम एक 't' हटाते हैं, तो तीन 's', दो 't' और दो 'u' होंगे, फिर से एक हटाएं, या तो 't' या 'u', उन्हें अच्छा बनाने के लिए।

समाधान के चरण

1. val := Counter(s) (s के प्रत्येक वर्ण की आवृत्ति वाला मैप)
2. res := 0
3. numlist := sorted(val.values())
4. i को 0 से len(numlist)-2 तक:
   • यदि numlist[i] नॉन-ज़ीरो है और numlist[i] == numlist[i+1]:
     • numlist[i] := numlist[i] - 1
     • res := res + 1
     • k := i-1
     • m := i
     • while numlist[m] and numlist[m] == numlist[k]:
       • numlist[k] := numlist[k] - 1
       • k := k - 1
       • m := m - 1
       • res := res + 1
5. res वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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