[Python] Explaining logic to myself O(N) Time O(1) Space (excluding the input array)
Before reading\nHello, everybody. I wrote this post to explain myself how I thought about it. I didn\'t finish during the contest, but I got this pertinent idea
## Before reading\nHello, everybody. I wrote this post to explain myself how I thought about it. I didn\'t finish during the contest, but I got this pertinent idea of how to solve it, and I did after resting :D. The idea is kind of blur, but I tried my best to explain my whole though process.\n## Ideas\nFor this question there is an interesting way to check if the `0`s and `1`s are well placed. Lets check the example `111000`:\n* The two possibilities for a correct placed `1` and `0` are `101010` and `010101`\n* You can also notice that, for `101010`, the idx of each `1` are even, and for every `0` they\'re odd\n* The opposite happens with  `010101`: `0`: even and `1`: odd\n\nFollowing the idea below we can easily check the number of misplaced `0` and `1` for the initial string:\n* Lets define `c0` the counter of misplaced `0` and `c1` the misplaced `1` \n```\nfor idx, c in enumerate(s):\n\tif idx & 1:\n\t\tif c == \'0\':\n\t\t\tc0 += 1\n\t\telse:\n\t\t\tc1 += 1\n\telse:\n\t\tif c == \'0\':\n\t\t\tc1 += 1\n\t\telse:\n\t\t\tc0 += 1\n```\n* The number of misplaced `0` and `1` are `c0` if starting with `0` and `c1` if starting with `1`\n\nOk, but how can we solve the question? Notice that we can do as much `Type-1` as we want. In other words, we want to count the number of misplaced in the `s = s + s` for every window of `size = len(s)`:\n* `111000 -> 111000111000`\n* `(111000)111000 -> c0 = 4, c1 = 2`, so in this step the `answer = min(c0, c1) = 2` \n* We want to run this check for every window of size `size` in the new `s`:\n* `1(110001)11000 -> c0 = 2, c1 = 4, ans = min([ans, c0, c1]) = 2`\n* And so it goes\n\nBut we still have a problem: The cost of this check is `O(N)`, so our algorithm will run in `O(N^2)`. Fortunately there is an interesting property here. Lets see what happens when we run the `Type-1` operation in our `101010` and  `010101`:\n* `101010 -> 010101`\n* `010101 -> 101010`\n* The pattern 1 became the pattern 2!!!. So, if we count `c1` comparing the pattern `101010` with s and the run `Type-1` on it, `c1 = c2` and vice versa.\n\nTo finish, the last thing we need to notice is that we can keep comparing the two pattern string with the current window but, everytime we shift the window, we need to shift the patterns as well:\n```\nStep 0:\n111000111000\n101010\n010101\n\nStep 1:\n111000111000\n 010101\n 101010\n \nStep 2:\n111000111000\n  101010\n  010101\n  \n (...)\n```\nIn that way we can know the number of misplaced values in O(1):\n1. Swap `c0, c1 = c1, c0`\n2. Since we swapped the values of `c0` and `c1`, we need to fix them in accord with the last state:\n\t1. To fix the new `c1`, we need to check if the first position of `s0` is different to the position that we want to remove. If it is, it means that the previous `c0` counts with it: `c1 -= 1`\n\t2. Now we\'re adding a new value to our window. Check if the last position of `s1` is different to this new value. If it is, `c1 += 1`. To sumarize: `c1 = c0 - (s0_start != to_remove) + (s1_end != to_add)`\n\t3. Same with `c0 = c1 - (s1_start != to_remove) + (s0_end != to_add)`\n\t4. Get the new answer: `ans = min([ans, c0, c1])` \n\n## Solution\nMy last code version with some optimizations:\n```\nclass Solution:\n    def minFlips(self, s: str) -> int:\n        size = len(s)\n        s1_start, s1_end = \'1\', \'1\' if size & 1 else \'0\'\n        s0_start, s0_end = \'0\', \'0\' if size & 1 else \'1\'\n        c0 = c1 = 0\n        for idx, c in enumerate(s):\n            c0 += ((c == \'0\' and idx & 1) or (c == \'1\' and (idx & 1 == 0)))\n            c1 += ((c == \'1\' and idx & 1) or (c == \'0\' and (idx & 1 == 0)))\n        ans = min(c0, c1)\n        for idx, c in enumerate(s):\n            c1, c0 = c0 - (s0_start != c) + (s1_end != c), c1 - (s1_start != c) + (s0_end != c)\n            ans = min([ans, c1, c0])\n        return ans\n```\n\nTime: O(N)\nSpace: O(1), considering that I didn\'t used any other data except the input s. But yes, the time should be O(N), where N is the lenght of the inputed arr\n\n## Explanations:\n### Start and End\n- The `s1_start` is always `1` and `s1_end` deppends on the lenght of `s`. Since I put `10` in pairs, if `s1_end = 1 if len(s) is odd else 0`\n- Same for `s0_start` and `s0_end`\n### The last iteration\nYou may noticed that my last iteration, i.e. the sliding window movement, is just another for. It happens because, since the windows size is equal to the `len(s)`, the new value that i\'ll add is `(len(s) + idx) % len(s) = idx` and the value that I\'m trying to remove is the `idx`, so I\'m removing the same value as the window start and adding it to windows end\n
[]