বাইনারি স্ট্রিংকে অ্যালটারনেটিং बनानेতে ন্যূনতম ফ্লিপ সংখ্যা বের করা

একটি বাইনারি স্ট্রিং s দেওয়া আছে। একটি অপারেশনে একটি বিট ফ্লিপ করা যায় (0→1 বা 1→0)। স্ট্রিংকে "অ্যালটারনেটিং" বলা হয় যদি কোনো দুটি সন্নিহিত ক্যারেক্টর একই না হয়। স্ট্রিংকে অ্যালটারনেটিং बनानेতে ন্যূনতম কতগুলো অপারেশন দরকার সেটা বের করতে হবে।

ইনপুট: s = "11100011" → আউটপুট: 3। ইনডেক্স 1, 4, 7-এ বিট ফ্লিপ করলে "10101010" হয়ে যাবে যা পূর্ণ অ্যালটারনেটিং।

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

change := 0
even_1, even_0, odd_1, odd_0 := 0 (কনজেক্টিভ কাউন্টার)
i = 0 থেকে len(s)-1 পর্যন্ত লুপ:
- যদি i জোড় (even): s[i]=='1' হলে even_1++, অন্যথায় even_0++
- যদি i বিজোড় (odd): s[i]=='1' হলে odd_1++, অন্যথায় odd_0++
দুটি প্যাটার্ন সম্ভব: "101010..." (even_1 + odd_0 ফ্লিপ) বা "010101..." (even_0 + odd_1 ফ্লিপ)
change = min(even_1 + odd_0, even_0 + odd_1)
change রিটার্ন করুন

উদাহরণ (Python)

def solve(s):
    change = 0
    even_1 = even_0 = odd_1 = odd_0 = 0
    for i in range(len(s)):
        if i % 2 == 0:
            if s[i] == '1': even_1 += 1
            else: even_0 += 1
        else:
            if s[i] == '1': odd_1 += 1
            else: odd_0 += 1
    if (even_1 + odd_0) > (even_0 + odd_1):
        change = even_0 + odd_1
    else:
        change = even_1 + odd_0
    return change

s = "11100011"
print(solve(s))

ইনপুট

"11100011"