मान लीजिए कि हमारे पास एक बाइनरी स्ट्रिंग है। हमें ज़्यादा से ज़्यादा एक "0" से "1" पर फ़्लिप करने की अनुमति है, हमें 1s के सबसे लंबे सन्निहित विकल्प की लंबाई ज्ञात करनी होगी।
इसलिए, यदि इनपुट s ="1010110001" जैसा है, तो आउटपुट 4 होगा, जैसे कि हम इंडेक्स 3 पर मौजूद शून्य को फ्लिप करते हैं, तो हमें "1011110001" स्ट्रिंग मिलती है, यहां 1s के सबसे लंबे सबस्ट्रिंग की लंबाई 4 है। ।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n :=आकार का
- उत्तर:=0, वाले:=0, बाएँ:=0, दाएँ:=0
- दाएं
- यदि s[दाएं] "1" के समान है, तो
- वाले :=वाले + 1
- जबकि दाएं - बाएं + 1 - वाले> 1, करें
- निकालें :=s[बाएं]
- यदि निकालें "1" के समान है, तो
- वाले :=वाले - 1
- बाएं:=बाएं + 1
- उत्तर :=अधिकतम उत्तर और (दाएं-बाएं + 1)
- दाएं:=दाएं + 1
- यदि s[दाएं] "1" के समान है, तो
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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))
इनपुट
"1010110001"
आउटपुट
4