पायथन में एक 0-फ्लिप के बाद बाइनरी स्ट्रिंग में 1s के सबसे लंबे सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट है s = "1010110001", तो आउटपुट 4 होगा, क्योंकि यदि हम इंडेक्स 3 पर मौजूद जीरो को फ्लिप करते हैं, तो हमें स्ट्रिंग "1011110001" मिलती है, यहां 1s के सबसे लंबे सबस्ट्रिंग की लंबाई 4 है।

एल्गोरिदम (स्लाइडिंग विंडो)

1. n := len(s)
2. ans := 0, ones := 0, left := 0, right := 0
3. while right < n:
   • यदि s[right] == "1", तो ones += 1
   • while (right - left + 1 - ones) > 1:
     • remove = s[left]
     • यदि remove == "1", तो ones -= 1
     • left += 1
   • ans = max(ans, right - left + 1)
   • right += 1
4. ans लौटाएं

उदाहरण कार्यान्वयन

def solve(s):
    n = len(s)
    ans = ones = left = right = 0
    while right < n:
        if s[right] == "1":
            ones += 1
        while right - left + 1 - ones > 1:
            remove = s[left]
            if remove == "1":
                ones -= 1
            left += 1
        ans = max(ans, right - left + 1)
        right += 1
    return ans

s = "1010110001"
print(solve(s))  # आउटपुट: 4

इनपुट

"1010110001"

आउटपुट

4