Python Solution O(N) Time, O(1) space, sliding window with Detailed Explanation!
We want to make several key observations here:\nAssuming we do not have access to operation 1, we want to find the \'difference\' between our input string s and
# We want to make several key observations here:\nAssuming we do not have access to operation 1, we want to find the* \'difference\'* between our input string s and an alternating string. \nWe have two alternating binary strings: either the alternating binary string that starts with 1: 10101.... or the binary string that starts with 0: 01010.....\nLet\'s say we are given the binary string \n\ns = "111000"\n\nNow let\'s calculate the different bits from s to both alternating binary strings (s is on top and alternating binary string is on the bottom):\n\n**1**1**10**0**0**\n**0**1**01**0**1**\ndiff_0 = 4\n\n1**1**10**0**0\n1**0**10**1**0\ndiff_1 = 2\n\nAs we can see here, the minimum number of flips between s and the alternating binary string starting with 1 is *2 flips.*\nAnother observation we can make here is that we only have to compute the number of flips between s and just **one** of the alternating binary strings since the other alternating binary string is the complement. Then the difference between s and the other alternating binary string that we did not keep track of is\n\n**len(s) - diff(alt binary str we kept track of)**\n\nAs we can see in the example above, diff_0 = len(s) - diff_1 ----> 4 = 6 - 2\n\nSo we go through the input string s once. That is O(N) time.  \n\n------------------\n\nNow what if consider operation 1??  Would that change the min number of flips?\n\nNotice that if N is even, then operation 1 does not change the minimum number of flips at all. For example:\ns = 10\nalt_b_str = 10\n\nnow move the first character (let\'s call it c) to the end of s. Here c = 1:\ns =  01\nalt_b_str = 01\n\nNotice that since N is even, the bit we are comparing c to stays the same, therefore, it will always take the same number of flips no matter how many operation 1s we do.\n\n-------------\n\nNow what if N is odd?\n\nconsider the binary string of length 3:\n\ns = "110"\n\nafter we go through the first loop, the minimum number of flips is 1:\n**1**10\n**0**10\n\nNow perform operation 1:\n101\n10**1**\n\nNotice that the bit in our alternating binary string changed, and now our min number of flips became 0!\n\nSo if N is odd, we can decrement the num flips if the character we move to the end is the same, otherwise we increment the number of flips like normal.\n\nWe can do Operation 1 a maximum of N times, so for each bit we \'move to the end\' of the string, update the minimum number of flips if it changed.\nBelow is each \'window\' that we keep track of after doing one Type-1 operation at each step\n\n```\n110 # original string (min_flips: 1)\n 101 # after first type-1 (min_flips: 0)\n  011 # after second type-1 (min_flips: 1)\n\t110 # after third type-1 (min_flips: 1)\n```\nThis is akin to appending the input string s back onto itself and then keeping track of a window of length N at each step in our loop\ni.e.\n110 + 110 = 110110\nwhere there are 4 windows to check for as shown above\n\nBut to simplify even further, we just have two loops where in the second loop starting from the begining of s again, we just update the minimum number of flips according to the first bit. \n\nSo we go through two passes of s to get a total time complexity of O(N)\n\n\n\n\n\n    def minFlips(self, s: str) -> int:\n        n = len(s)\n        diff_first_str = 0\n        first_str_bit = 0\n        \n        # go through first pass to check minimum number of operation 2 (if operation 1 was not done)\n        for c in s:\n            if int(c) != first_str_bit:\n                diff_first_str += 1\n            first_str_bit = not first_str_bit\n        \n        min_diff = min(diff_first_str, n - diff_first_str)\n        \n        # operation 1 only matters if n is odd, then use sliding window to chec\n        if n%2 != 0:\n            for c in s:\n                if int(c) == first_str_bit:\n                    diff_first_str -= 1\n                else:\n                    diff_first_str += 1\n                \n                min_diff = min(min_diff, diff_first_str, n - diff_first_str)\n                first_str_bit = not first_str_bit\n                \n        return min_diff\n
[]