পাইথনে স্ট্রিংকে ভারসাম্যপূর্ণ করতে ন্যূনতম মুছে ফেলার জন্য প্রোগ্রাম

ধরুন আমাদের একটি স্ট্রিং s আছে মাত্র দুটি অক্ষর আছে 's' এবং 't'। স্ট্রিংটিকে সুষম করতে আমরা s-এর যেকোনো সংখ্যক অক্ষর মুছে ফেলতে পারি। আমরা বলতে পারি, s ভারসাম্যপূর্ণ হয় যখন কোনো জোড়া সূচক (i,j) না থাকে যেমন i

সুতরাং, যদি ইনপুটটি s ="sststtst" এর মত হয়, তাহলে আউটপুট হবে 2 কারণ আমরা হয়, সূচক 2 এবং 6 ("sststtst" থেকে "sssttt") অক্ষরগুলি সরিয়ে ফেলতে পারি, অথবা সূচক 3 থেকে অক্ষরগুলি সরিয়ে দিতে পারি এবং 6 ("sststtst" থেকে "sstttt")।

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

cum_b :=0
count_a :=s
-এ 's' অক্ষরের সংখ্যা
উত্তর :=অসীম
প্রতিটি x এর জন্য s, করুন
- যদি x "s" এর মত হয়, তাহলে
  - count_a :=count_a - 1
  - ans :=সর্বনিম্ন উত্তর এবং (cum_b + count_a)
- অন্যথায়,
  - cum_b :=cum_b + 1
  - উত্তর :=সর্বনিম্ন উত্তর এবং (cum_b-1 + count_a)
উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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"