मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग है, और हम किन्हीं दो बिट्स को स्वैप कर सकते हैं। हमें सभी 1s को एक साथ ग्रुप करने के लिए आवश्यक न्यूनतम स्वैप की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट s = "0111001" है, तो आउटपुट 1 होगा, क्योंकि हम ये स्वैप कर सकते हैं: 0111001 -> 1111000।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम स्लाइडिंग विंडो और प्रीफिक्स सम का उपयोग करेंगे:
- data := दी गई बाइनरी स्ट्रिंग से 0s और 1s की लिस्ट
- one := 0, n := data सरणी की लंबाई
- summ आकार n की सरणी बनाएं, 0 से भरें, summ[0] := data[0]
- one := one + data[0]
- i को 1 से n-1 तक लूप चलाएं:
- summ[i] := summ[i-1] + data[i]
- one := one + data[i]
- ans := one
- left := 0, right := one - 1
- जब तक right < n:
- यदि left 0 है, तो temp := summ[right], अन्यथा temp := summ[right] - summ[left-1]
- ans := min(ans, one - temp)
- right और left को 1 से बढ़ाएं
- ans लौटाएं
पायथन कार्यान्वयन
class Solution(object):
def solve(self, s):
data = list(map(int, list(s)))
one = 0
n = len(data)
summ = [0 for i in range(n)]
summ[0] = data[0]
one += data[0]
for i in range(1, n):
summ[i] = summ[i-1] + data[i]
one += data[i]
ans = one
left = 0
right = one - 1
while right < n:
if left == 0:
temp = summ[right]
else:
temp = summ[right] - summ[left-1]
ans = min(ans, one - temp)
right += 1
left += 1
return ans
ob = Solution()
s = "0111001"
print(ob.solve(s))इनपुट
"0111001"
आउटपुट
1
