পাইথনে বিভিন্ন সংলগ্ন বিট মুছে ফেলার পর সংক্ষিপ্ততম স্ট্রিং খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুটটি s ="1100011" এর মত হয়, তাহলে আউটপুট হবে 1, যেমন "10" মুছে ফেলার পরে আমরা "10011" পাব, তারপর আবার "10" মুছুন, এটি "011" হবে, তারপর "01" মুছুন। ", এটি 1 বাকি থাকবে।

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

স্ট্যাক :=একটি নতুন তালিকা
s-এ প্রতিটি c-এর জন্য, করুন
- যদি স্ট্যাক খালি হয় বা স্ট্যাকের উপরের অংশটি c এর মত হয়, তাহলে
  - স্ট্যাকের মধ্যে সি পুশ করুন
- অন্যথায় যখন স্ট্যাকের টপ সি এর মত না হয়, তখন
  - স্ট্যাক থেকে পপ উপাদান
স্ট্যাকে উপাদান গণনা ফেরত দেয়

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

উদাহরণ

class Solution:
   def solve(self, s):
      stack = []
      for c in s:
         if not stack or stack[-1] == c:
            stack.append(c)
         elif stack[-1] != c:
            stack.pop()
      return len(stack)
ob = Solution() print(ob.solve("1100011"))

ইনপুট

"1100011"