पायथन में एक जोड़ी बिट्स स्वैप करके सबसे लंबे 1s की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग s है। यदि हम स्ट्रिंग में अधिकतम एक जोड़ी वर्णों को स्वैप कर सकते हैं, तो हमें परिणामी सबसे लंबे सन्निहित 1s के सबस्ट्रिंग की लंबाई ढूंढनी है।

उदाहरण के लिए, यदि इनपुट s = "1111011111" है, तो आउटपुट 9 होगा, क्योंकि हम s[4] और s[9] को स्वैप करके 9 लगातार 1s प्राप्त कर सकते हैं।

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

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (स्लाइडिंग विंडो अधिकतम 1 जीरो के साथ):

• l := 0, cnt := 0, ans := 0
• r को 0 से len(s) तक:
  • cnt += (1 if s[r]=='0' else 0)
  • यदि cnt > 1:
    • cnt -= (1 if s[l]=='0' else 0)
    • l += 1
  • ans := max(ans, r-l+1)
• min(ans, s.count('1')) लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, s):
        l = 0
        cnt = 0
        ans = 0
        for r in range(len(s)):
            cnt += s[r] == "0"
            if cnt > 1:
                cnt -= s[l] == "0"
                l += 1
            ans = max(ans, r - l + 1)
        return min(ans, s.count("1"))

ob = Solution()
s = "1111011111"
print(ob.solve(s))

इनपुट

"1111011111"

आउटपुट

9