পাইথনে ক্যারেক্টার ফ্রিকোয়েন্সি ইউনিক করার ন্যূনতম ডিলিশন গণনার প্রোগ্রাম

মান লিজিয়ে একটি স্ট্রিং আছে s। s কে good বলা হয় যদি সেটিতে দুটি ভিন্ন ক্যারেক্টারের ফ্রিকোয়েন্সি একই না হয়। s-কে good बनानेোর জন্য ন্যূনতম কত ক্যারেক্টার ডিলিট করতে হবে সেটি বের করতে হবে।

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

সমাধানের ধাপসমূহ

• val := Counter(s)

• res := 0

• numlist := sorted(val.values())

• i = 0 থেকে len(numlist)-2 পর্যন্ত:

  • যদি numlist[i] নন-জিরো এবং numlist[i] == numlist[i+1] হয়, তবে:

    • numlist[i] -= 1, res += 1

    • k := i-1, m := i

    • numlist[m] নন-জিরো এবং numlist[m] == numlist[k] থাকা পর্যন্ত:

      • numlist[k] -= 1, k -= 1, m -= 1, res += 1

• 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