পাইথনের বাইনারি স্ট্রিং থেকে 10 বা 01 সরিয়ে দিয়ে আমরা কীভাবে সর্বাধিক স্কোর পেতে পারি তা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি স্ট্রিং s এবং দুটি মান zero_one এবং one_zero আছে। এখন একটি অপারেশন বিবেচনা করা যাক যেখানে আমরা যেকোনো সাবস্ট্রিং "01" মুছে ফেলতে পারি এবং zero_one পয়েন্ট পেতে পারি। অথবা আমরা যেকোনো সাবস্ট্রিং "10" মুছে ফেলতে পারি এবং এক_শূন্য পয়েন্ট পেতে পারি। যেকোন সংখ্যক অপারেশনের পরে আমরা সর্বোচ্চ কত পয়েন্ট পেতে পারি তা আমাদের খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="10100101" zero_one =3 one_zero =2 এর মত হয়, তাহলে আউটপুট হবে 11, কারণ আমরা 3*3 =9 পয়েন্ট পেতে "01" তিনবার সরিয়ে ফেলতে পারি। তারপর অবশিষ্ট স্ট্রিং হল 10। এটিকে সরিয়ে দিয়ে আমরা আরও 2 পয়েন্ট পেতে পারি যাতে মোট 11 হয়।

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

A :=ইনপুট স্ট্রিং হিসাবে দেওয়া বিটের একটি তালিকা
যদি zero_one
- zero_one এবং one_zero
  অদলবদল করুন
- আমি 0 থেকে A এর আকারের মধ্যে, কর
  - A[i] :=A[i] XOR 1
উত্তর :=0
স্ট্যাক :=একটি নতুন স্ট্যাক
A-তে প্রতিটি x এর জন্য করুন
- স্ট্যাক খালি না হলে এবং স্ট্যাক শীর্ষ উপাদান
  - স্ট্যাক থেকে পপ
  - ans :=ans + zero_one
- অন্যথায়,
  - x স্ট্যাকের মধ্যে পুশ করুন
ans :=ans + one_zero * স্ট্যাকে ন্যূনতম 0 এবং স্ট্যাকের মধ্যে 1 এর উপস্থিতি
উত্তর ফেরত দিন

উদাহরণ (পাইথন)

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

class Solution:
   def solve(self, S, zero_one, one_zero):
      A = list(map(int, S))
      if zero_one < one_zero:
         zero_one, one_zero = one_zero, zero_one
         for i in range(len(A)):
            A[i] ^= 1
         ans = 0
         stack = []
         for x in A:
            if stack and stack[-1] < x:
               stack.pop()
               ans += zero_one
            else:
               stack.append(x)
         ans += one_zero * min(stack.count(0), stack.count(1))
         return ans
ob = Solution()
s = "10100101"
zero_one = 3
one_zero = 2
print(ob.solve(s, zero_one, one_zero))

ইনপুট

"10100101", 3, 2