পাইথনে বাইনারি স্ট্রিং-এ সব ১ একসাথে আনার জন্য ন্যূনতম সওয়াপ সংখ্যা বের করার প্রোগ্রাম

একটি বাইনারি স্ট্রিং দেওয়া আছে। যেকোনো দুটি বিট সওয়াপ করা যাবে। সকল ১ কে একসাথে (কন্টিগুয়াস) আনার জন্য ন্যূনতম সওয়াপ সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, s = "0111001" হলে আউটপুট ১, কারণ 0111001 → 1111000 (একটি সওয়াপ)।

সমাধানের পদ্ধতি (স্লাইডিং উইন্ডো + প্রিফিক্স সাম)

1. স্ট্রিংকে ইন্টিজার অ্যারে data-এ কনভার্ট করুন।
2. one = মোট ১-এর সংখ্যা।
3. summ = প্রিফিক্স সাম অ্যারে।
4. আকার one-এর স্লাইডিং উইন্ডো স্লাইড করুন। প্রতিটি উইন্ডোতে কতটি ১ আছে সেটি বের করুন: temp = summ[right] - (summ[left-1] if left>0 else 0)।
5. সওয়াপ লাগবে one - temp (উইন্ডোর বাইরের ১গুলো উইন্ডোর ভেতরে আনা লাগবে)। ন্যূনতম মান রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution(object):
    def solve(self, s):
        data = list(map(int, list(s)))
        one = 0
        n = len(data)
        summ = [0]*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