पायथन में बाइनरी स्ट्रिंग से 10 या 01 को हटाकर हम अधिकतम स्कोर कैसे प्राप्त कर सकते हैं, यह जानने के लिए कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है और दो मान शून्य_एक और एक_शून्य हैं। अब आइए एक ऑपरेशन पर विचार करें जहां हम किसी भी सबस्ट्रिंग "01" को हटा सकते हैं और शून्य_एक अंक प्राप्त कर सकते हैं। या हम किसी भी सबस्ट्रिंग "10" को हटा सकते हैं और one_zero अंक प्राप्त कर सकते हैं। हमें किसी भी ऑपरेशन के बाद अधिकतम अंक प्राप्त करने होंगे।

इसलिए, यदि इनपुट s ="10100101" Zero_one =3 one_zero =2 जैसा है, तो आउटपुट 11 होगा, क्योंकि हम 3*3 =9 अंक प्राप्त करने के लिए "01" को तीन बार हटा सकते हैं। फिर शेष स्ट्रिंग 10 है। इसे हटाकर हम 2 अंक प्राप्त कर सकते हैं ताकि कुल 11 हो।

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

• A:=इनपुट स्ट्रिंग के रूप में दिए गए बिट्स की सूची

• अगर शून्य_एक

  • शून्य_एक और एक_शून्य को स्वैप करें

  • मैं के लिए 0 से ए के आकार की सीमा में, ऐसा करें

    • ए[i] :=ए[i] XOR 1

• उत्तर :=0

• स्टैक :=एक नया स्टैक

• A में प्रत्येक x के लिए, करें

  • यदि स्टैक खाली नहीं है और स्टैक शीर्ष तत्व

    • स्टैक से पॉप करें

    • उत्तर:=उत्तर + जीरो_ऑन

  • अन्यथा,

    • x को स्टैक में पुश करें

• उत्तर:=उत्तर + 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

आउटपुट

11