पायथन में स्ट्रिंग को संतुलित करने के लिए न्यूनतम विलोपन खोजने का कार्यक्रम

मान लीजिए कि हमारे पास केवल दो अक्षर 's' और 't' के साथ एक स्ट्रिंग है। स्ट्रिंग को संतुलित बनाने के लिए हम s के किसी भी वर्ण को हटा सकते हैं। हम कह सकते हैं, s संतुलित है जब सूचकांकों की कोई जोड़ी नहीं है (i,j) जैसे कि i

इसलिए, यदि इनपुट s ="sststtst" जैसा है, तो आउटपुट 2 होगा क्योंकि हम या तो, इंडेक्स 2 और 6 ("sststtst" से "sssttt") पर वर्णों को हटा सकते हैं, या इंडेक्स 3 पर वर्णों को हटा सकते हैं और 6 ("sststtst" से "sstttt")।

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

• कम_बी:=0

• count_a :=अक्षर 's' की संख्या s

  . में

• उत्तर:=अनंत

• प्रत्येक x in s के लिए, करें

  • यदि x "s" के समान है, तो

    • count_a :=count_a - 1

    • उत्तर:=न्यूनतम उत्तर और (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"

आउटपुट

2