पायथन में बाइनरी स्ट्रिंग को दो भागों में विभाजित करके अधिकतम स्कोर ढूंढना

मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग s है। अब एक ऑपरेशन पर विचार करें, जहां हम स्ट्रिंग को दो नॉन-खाली सबस्ट्रिंग s1 और s2 में विभाजित करते हैं। इस विभाजन का स्कोर s1 में "0" की संख्या का योग और s2 में "1" की संख्या का योग है। हमें अधिकतम स्कोर ढूंढना है जो हम प्राप्त कर सकते हैं।

उदाहरण के लिए, यदि इनपुट है s = "011001100111", तो आउटपुट होगा 8, क्योंकि हम स्ट्रिंग को "01100" + "110111" की तरह विभाजित कर सकते हैं। तब, स्कोर 3 + 5 = 8 है।

समाधान दृष्टिकोण

यह एक सरल लीनियर स्कैन समस्या है। हम कुल 1 की संख्या गिनते हैं, फिर बाएं से दाएं स्कैन करते हुए 0 की गिनती बढ़ाते हैं और 1 की गिनती घटाते हैं, प्रत्येक पोजीशन पर अधिकतम स्कोर ट्रैक करते हैं।

• ones = स्ट्रिंग में कुल 1 की संख्या।
• zeros = 0 से आरंभ करें।
• प्रत्येक इंडेक्स i (अंतिम को छोड़कर) के लिए:
  • यदि s[i] == '0', zeros बढ़ाएं।
  • अन्यथा ones घटाएं।
  • ans = max(ans, ones + zeros) अपडेट करें।

पायथन कार्यान्वयन

def solve(s):
    ones = s.count("1")
    zeros = 0
    ans = 0
    for i in range(len(s) - 1):
        if s[i] == "0":
            zeros += 1
        else:
            ones -= 1
        ans = max(ans, ones + zeros)
    return ans

s = "011001100111"
print(solve(s))

इनपुट

"011001100111"

आउटपुट

8