পাইথনে স্ট্রিং ব্যালেন্সড করার ন্যূনতম ডিলিশন বের করার প্রোগ্রাম

মান লিজিয়ে আমাদের একটি স্ট্রিং আছে s যাতে শুধু 's' এবং 't' এই দুটি ক্যারেক্টার রয়েছে। আমরা s-এর যেকোনো সংখ্যক ক্যারেক্টার ডিলিট করে স্ট্রিংটিকে ব্যালেন্সড করতে পারি। একটি স্ট্রিং ব্যালেন্সড বলা হয় যখন কোনো ইন্ডেক্স জোড়া (i,j) নেই যাতে i < j এবং s[i] = 't' এবং s[j] = 's'। ন্যূনতম কত ডিলিশন লাগবে সেটি বের করতে হবে।

যেমন, ইনপুট হলে s = "sststtst", তবে আউটপুট হবে 2 কারণ আমরা হয় ইন্ডেক্স ২ ও ৬ মুছে দিতে পারি ("sststtst" -> "sssttt"), অথবা ইন্ডেক্স ৩ ও ৬ মুছে দিতে পারি ("sststtst" -> "sstttt")।

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

• cum_b := 0

• count_a := s.count('s')

• ans := infinity

• s-এ প্রতিটি x এর জন্য:

  • যদি x == "s" হয়, তবে: count_a -= 1, ans = min(ans, cum_b + count_a)

  • অন্যথায়: cum_b += 1, ans = min(ans, cum_b - 1 + count_a)

• ans রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(s):
    cum_b = 0
    count_a = s.count("s")
    ans = float("inf")
    for x in s:
        if x == "s":
            count_a -= 1
            ans = min(ans, cum_b + count_a)
        else:
            cum_b += 1
            ans = min(ans, cum_b - 1 + count_a)
    return ans

s = "sststtst"
print(solve(s))

ইনপুট

"sststtst"

আউটপুট

2