পাইথনে বাইনারি স্ট্রিং-এ বारी-बারি মান পেতে কমপক্ষে কত ফ্লিপ দরকার সেটি বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি স্ট্রিং s আছে। এখন আমরা s-র কিছু প্রিফিক্স নিয়ে তা পেছনে সরাতে পারি। এরপর স্ট্রিং-এ একে পরে একই মান থাক না, সেজন্য কমপক্ষে কত ক্যারেক্টার ফ্লিপ করতে হবে তা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট s = "10010101111" হলে আউটপুট হবে 2, কারণ আমরা প্রিফিক্স "10" নিয়ে পেছনে দিতে পারি, তাহলে স্ট্রিং হবে "01010111110"। তারপর ডান পাশ থেকে ৩য় ও ৫য় বিট 0 করে ফ্লিপ করলে পাব "01010101010"।

সমাধানের ধাপসমূহ

• ans := S-এর আকার
• N := S-এর আকার
• s := 0
• i = 0 থেকে 2*N-1 পর্যন্ত লুপ চালান:
  • s := s + (S[i mod N] XOR (i AND 1))-এর ইন্টিজার মান
  • যদি i >= N-1 হয়:
    • ans := min(ans, s, N-s)
    • s := s - (S[(i-(N-1)) mod N] XOR ((i-(N-1)) AND 1))-এর ইন্টিজার মান
• ans রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:

class Solution:
    def solve(self, S):
        ans = N = len(S)
        s = 0
        for i in range(2 * N):
            s += int(S[i % N]) ^ (i & 1)
            if i >= N - 1:
                ans = min(ans, s, N - s)
                s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
        return ans

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

ইনপুট

"10010101111"

আউটপুট

2