Beats 96% | Python | Explained | O(n) | No sliding window or dp
Intuition\n\nFew observations at first:\n- The problem essentially breaks down to weather to start the string with "0" or "1".\n- If there are odd nos of elemen
# Intuition\n\nFew observations at first:\n- The problem essentially breaks down to weather to start the string with "0" or "1".\n- If there are odd nos of elements, the start and end characters will always be the same after re-arranging.\n- If even, start and end will be different.\n\nIf we for now forget about the 1st clause to make the problem simpler we will notice that we can easily find out the number of misplaced elements for a case of string starting with "0" (over a single iteration), and to find out the same for string starting with "1", we can simply do:\n```\nn - (no of missplaced elems if str starts with "0")\n```\nAnd the min of both will be the answer.\n\nNow comes the 1st clause, we notice that we can optimize our answer even further in certain cases if we apply the 1st clause. How?\n\nImagine str starts with 0, but we are currently considering a case where start should have been 1 (i.e  str[1] should be 0 and so on). \n```\nActual:\n0110..n\nShould have been:\n1010..n\nDiff (Y: yes, N: no):\nYYNN..n\n\n--After replacing 1st elem to the end--\nActual:\n110..0\nShould have been (maintaing the diff sequence):\n010..0 (if str length is odd)\n010..1 (if str length is even)\n```\nThis means str[0] (i.e 0) needs to be reversed. Let\'s say for this case we have (r) such misplaced elements. But since our goal is to reduce r, what if we apply the 1st clause and put it at the end? Will it be of any use?\n\nThere can be 2 cases here:\n- String is even: here after putting the 1st elem "0" at the end, now the 1st element should be "1" for same r. But as we observed before, for even, first and last elements should be the same, thus the "0" that we just removed and put at the end needs to be converted to "1" again. Thus, we see there is no net change in r, since ultimately we had to reverse that "0" anyway.\n- String is odd: here we do the same thing, put the 1st "0" at the end, thus now the 1st element should be "1" if we try to keep r the same. But we notice that unlike the previous case we already have the desired element at the end, i.e "0", thus we can say we have successfully reduced one inversion that would have happened otherwise, i.e r=r-1.\n\n# Approach\n\n- We first find out r for both cases (i.e if we consider start=0 or start=1).\n- If the length of string is even, we just return the least of both r, since we have already proved this case cannot be optimized further.\n- We continue for odd length:\n- For both cases of start=0,1 we do:\n- iterate over each index of the string, and each step we are considering as if the current start element is moved to the end.\n- By moving, 2 situations can occur, we are moved an element that is already correct, thus now it becomes incorrect (since the next elem becomes start, and it will not be equal to the current one but for odd lengths it should have been equal), thus r=r+1. Or it was incorrect, thus now by moving it to end actually helps (as discussed earlier), i.e r=r-1.\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```\nclass Solution:\n    def minFlips(self, s: str) -> int:\n        n = len(s)\n        r0 = 0\n        curr = \'0\'\n        for i in range(n):\n            if s[i]!=curr:\n                r0+=1\n            curr = \'1\' if curr==\'0\' else \'0\'\n        r1 = n - r0\n        if n%2==0:\n            return min(r0,r1)\n        def minn(r,curr):\n            res = r\n            for i in range(n):\n                if curr!=s[i]:\n                    r-=1\n                else:\n                    r+=1\n                res = min(res,r)\n                curr = \'0\' if curr==\'1\' else \'1\'\n            res = min(res,r)\n            return res\n        return min(minn(r0,\'0\'),minn(r1,\'1\'))\n\n```
['Python3']