पायथन में वैकल्पिक मान प्राप्त करने के लिए आवश्यक न्यूनतम फ्लिप की संख्या ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग s है। मान लीजिए हम s का कोई उपसर्ग ले सकते हैं और उसे पीछे ले जा सकते हैं। फिर, उन वर्णों की न्यूनतम संख्या ज्ञात करें जिन्हें फ्लिप करने की आवश्यकता है ताकि कोई लगातार वर्ण समान मान के न हों।

उदाहरण के लिए, s = "10010101111" के लिए आउटपुट 2 होगा। हम उपसर्ग "10" को पीछे ले जा सकते हैं, स्ट्रिंग बन जाती है "01010111110", फिर दाएं से 3वें और 5वें बिट को 0 पर फ्लिप करके "01010101010" प्राप्त कर सकते हैं।

एल्गोरिदम (स्लाइडिंग विंडो)

• ans := len(S), N := len(S), s := 0
• i = 0 से 2*N-1 तक:
  • s += int(S[i%N]) ^ (i & 1)
  • यदि i >= N-1:
    • ans = min(ans, s, N-s)
    • s -= int(S[(i-(N-1))%N]) ^ ((i-(N-1)) & 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