পাইথনে অক্ষর ফ্রিকোয়েন্সি অনন্য করার জন্য প্রয়োজনীয় ন্যূনতম মুছে ফেলার গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে, s-কে ভাল বলা হয় যদি s-এ একই কম্পাঙ্কের দুটি ভিন্ন অক্ষর না থাকে। একটি ভাল স্ট্রিং তৈরি করতে আমাদের ন্যূনতম কতগুলি অক্ষর মুছে ফেলতে হবে তা খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুটটি s ="ssstttuu" এর মত হয়, তাহলে আউটপুট হবে 2 কারণ আমরা যদি একটি 't' মুছে ফেলি, তাহলে তিনটি 's', দুটি 't' এবং দুটি 'u' হবে, তারপর আবার মুছে ফেলুন। একটি, হয় 't' বা 'উ', সেগুলিকে ভাল করতে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• val :=s এর প্রতিটি অক্ষরের ফ্রিকোয়েন্সি সম্বলিত একটি নতুন মানচিত্র
• res :=0
• numlist :=ভ্যাল থেকে সমস্ত ফ্রিকোয়েন্সি মানের তালিকা সাজান
• আমি 0 থেকে numlist -2 এর আকারের মধ্যে, কর
  • যদি numlist[i] অ শূন্য হয় এবং numlist[i] numlist[i+1] এর মত হয়, তাহলে
    • numlist[i] :=numlist[i] - 1
    • res :=res + 1
    • k :=i-1
    • m :=i
    • যদিও numlist[m] অ-শূন্য এবং numlist[m] numlist[k] এর মতই, do
      • numlist[k] :=numlist[k] - 1
      • k :=k - 1
      • m :=m - 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