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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• val :=एक नया नक्शा जिसमें s के प्रत्येक वर्ण की आवृत्ति होती है
• res :=0
• numlist :=वैल से सभी फ़्रीक्वेंसी मानों की सूची को सॉर्ट करें
• मेरे लिए 0 से लेकर अंकसूची -2 के आकार तक, करें
  • यदि numlist[i] शून्य नहीं है और numlist[i] numlist[i+1] के समान है, तो
    • numlist[i] :=numlist[i] - 1
    • रेस :=रेस + 1
    • k :=i-1
    • एम:=मैं
    • जबकि numlist[m] गैर-शून्य है और numlist[m] numlist[k] के समान है, do
      • numlist[k] :=numlist[k] - 1
      • k :=k - 1
      • एम :=एम - 1
      • रेस :=रेस + 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