Python में अल्टरनेटिंग बाइनरी स्ट्रिंग के लिए न्यूनतम परिवर्तन खोजें

मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग s है। एक ऑपरेशन पर विचार करें जहां हम एक बिट फ्लिप कर सकते हैं। स्ट्रिंग s को अल्टरनेटिंग स्ट्रिंग कहा जाता है यदि कोई दो आसन्न कैरेक्टर समान नहीं हैं। हमें s को अल्टरनेटिंग बनाने के लिए आवश्यक न्यूनतम ऑपरेशन्स की संख्या ढूंढनी है।

इसलिए, यदि इनपुट है: s = "11100011", तो आउटपुट 3 होगा क्योंकि यदि हम पोजीशन 1, 4 और 7 पर बिट्स फ्लिप करते हैं, तो यह "10101010" बन जाएगा, फिर सभी अल्टरनेटिंग हैं।

हल करने के चरण

1. change := 0
2. even_1 := 0, even_0 := 0
3. odd_1 := 0, odd_0 := 0
4. i को 0 से s के आकार - 1 तक के लिए:
   • यदि i सम है:
     • यदि s[i] == '1', तो even_1++
     • अन्यथा even_0++
   • अन्यथा:
     • यदि s[i] == '1', तो odd_1++
     • अन्यथा odd_0++
5. यदि (even_1 + odd_0) > (even_0 + odd_1), तो change := even_0 + odd_1
6. अन्यथा, change := even_1 + odd_0
7. change वापस करें

उदाहरण (Python)

def solve(s):
    change = 0
    even_1 = 0
    even_0 = 0
    odd_1 = 0
    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"

आउटपुट

3