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

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

उदाहरण के लिए, s = "10100101", zero_one=3, one_zero=2 के लिए आउटपुट 11 होगा।

एल्गोरिदम (स्टैक आधारित ग्रीडी)

A := इनपुट स्ट्रिंग से बिट्स की सूची
यदि zero_one < one_zero, तो उन्हें स्वैप करें और A में सभी बिट्स को फ्लिप करें
ans := 0, stack := []
प्रत्येक x in A के लिए:
- यदि स्टैक खाली नहीं है और stack[-1] < x (यानी "01" पैटर्न), तो पॉप करें, ans += zero_one
- अन्यथा x को स्टैक में डालें
ans += one_zero * min(stack.count(0), stack.count(1))
ans वापस करें

उदाहरण

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