Simple Python3 Solution | 99.9% | Sliding Window | Simple And Elegant With Explanation.
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is to find the minimum number of flips needed to make a given binary string
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to find the minimum number of flips needed to make a given binary string have alternating characters. The solution aims to achieve this by considering two possible alternate patterns: one starting with "0" and the other starting with "1". Then, it iterates through the string while keeping track of the differences between the original string and these two alternate patterns. The goal is to find the minimum number of differences at any position that matches the length of the original string.\n\n---\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Calculate the length of the input string n.\n\n2. Duplicate the input string by concatenating it with itself (s = s + s). This doubling of the string helps handle circular cases more easily.\n\n3. Initialize two alternate patterns, alt1 and alt2, where each character alternates between "0" and "1" (starting with different characters).\n\n4. Initialize variables: res to store the minimum number of flips needed, l to track the left end of the current substring, diff1 and diff2 to track the differences between the substring and the two alternate patterns.\n\n5. Iterate through the string using the variable r as the right end of the substring.\n\n- Update diff1 and diff2 by comparing the current character with the corresponding characters in alt1 and alt2.\n- If the length of the current substring is greater than n, adjust the differences by removing the contribution of the leftmost character (s[l]) from the counts.\n- If the length of the current substring is exactly n, update res with the minimum of the current values of res, diff1, and diff2. This accounts for the possibility of flipping a substring with the minimum differences.\n\n6. Finally, return the value of res, which represents the minimum number of flips needed to create an alternating pattern of characters.\n\n---\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\nBeats 88.65% of Python3 Users\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\nBeats 87.33% of Python Users\n\n---\n\n\n# Code\n```\nclass Solution:\n    def minFlips(self, s: str) -> int:\n        n = len(s)\n        s = s + s\n        alt1 , alt2 = " " , " "\n\n        for i in range(len(s)):\n            alt1 += "0" if i % 2 else "1"\n            alt2 += "1" if i % 2 else "0"\n\n        res = len(s)\n        l = 0\n        diff1 , diff2 = 0 , 0 \n        for r in range(len(s)):\n            if s[r] != alt1[r]:\n                diff1 +=1\n            if s[r] != alt2[r]:\n                diff2 +=1\n\n            if (r-l+1) > n:\n                if s[l] != alt1[l]:\n                    diff1-=1\n                if s[l] != alt2[l]:\n                    diff2-=1\n                l+=1\n\n            if (r-l+1) == n:\n                res = min(res,diff1,diff2)\n        return res\n            \n            \n```
['String', 'Sliding Window', 'Python3']