Python - Fixed Size Sliding Window - EXPLAINED
For me it was quite a tricky question to understand but thanks to some help from Leetcode Discussion and YouTube, I got the main idea of this problem. And Now I
For me it was quite a tricky question to understand but thanks to some help from Leetcode Discussion and YouTube, I got the main idea of this problem. And Now I feel too dumb to not get it myself xD\n\nAnyways, here is an explanation of what we have to do. \n\nWe are given a binary string and we want to make it alternating. Alternating means each 0 after each 1 and 1 after each 0. e.g. for a binary string of length = 3, we have two valid alternating string -> 101 and 010. In fact, for every length, there are only two valid alternting strings which is obvious because there are only two types of numbers in a binary string - 1 and 0.\n\nFor a moment, forget that type-1 operation exists. Just think that we are given a string and we can flip a bit. We want to find minimum number of flips we can do so that this string is alternating. How will you do it? Will you take each bit, flip it and check if that makes string alternating? Ofcourse not. \n\nBecause we know that for any length, there are only two valid alternating strings, we can simply compare each position with each valid string. And if the number at that position differs, we need to flip. In other words -\n\n\t\tMinimum Number of Flips = Minimum Number of differences between given string and valid strings\n\n\t\tlets say s = "111000"\n\nSince length is 6, what are the valid alternating binary strings of length 6? They are \n\t\t\n\t\t\tvalid1 = "101010"\n\t\t\tvalid2 = "010101"\n\nSo, lets compare s with valid1 first\n\n\t\t\ts =      "111000"\n\t\t\tvalid1 = "101010"\n\t\t\t\n\t\t\tFor each position in s, check what is the value at same position in valid1. If they are not same, we need to flip.\n\t\t\t\n\t\t\tSo we get differences = 2\n\t\nNow lets compare s with valid2\n\t\t\t\n\t\t\ts =      "111000"\n\t\t\tvalid1 = "010101"\n\t\t\t\t\t\t\n\t\t\tWe get differences = 4\n\t\t\t\nSo that means, we can simply flip 2 bits to make the string alternating such that it starts with 1, instead of flipping 4 bits such that it starts with 0.\n\nNow we add in the type-1 operation. It says that we can take a character from beginning of string "s" and add it to the end of it in order to minimize the flips. What that means?\n\n\tLets say we performed type-1 operation once on s = "111000"\n\tThen the first "1" will be moved to end. So string will become "110001"\n\t\n\tAnd now again, we have to do the same thing as above \n\ti.e., compare it with valid1 and valid2 to see which one results in least difference.\n\t\nWhat is the maximum number of type-1 operations we can do? It is equal to length of string. Why? Because if we take the whole string and append it to itself, that means we get the same string in return.\n\n\ts = "111000" \n\t1 type-1 operation, s = "110001"\n\t2 type-1 operations, s = "100011"\n\t3 type-1 operations, s = "000111"\n\t4 type-1 operations, s = "001110"\n\t5 type-1 operations, s = "011100"\n\t6 type-1 operations, s = "111000" => Back to original\n\t\nSo it makes no sense to go above 6 in this case as we would be doing the same work again. \n\nSo that means, instead of manually taking each character and moving it to end, why not we double the given string "s" .\n\n\ts = "111000" to s + s\n\tsuch that new s => "111000111000"\n\t\n\tAnd now, each window of size = 6 represents each type-1 operation.\n\t\n\tFirst window of size 6 -> "111000"\n\tSecond window of size 6 -> "110001"\n\tThird window of size 6 -> "100011"\n\tFourth window of size 6 -> "000111"\n\tFifth window of size 6 -> "001110"\n\tSixth window of size 6 -> "011100"\n\tSeventh window of size 6 -> "111000" => Back to original\n\t\nSo we had to do no extra work to take each character from beginning and move it to end.\n\nAnd now. Just think how we were comparing the string with valid1 and valid2.\n\n\t\ts =      "111000"\n\t\tvalid1 = "101010"\n\t\tDifferences = 2\n\t\t\nWhen we take a character out from "s" and move it to end, then that means, we need to do the same with valid1 right? Because we won\'t be recalculating the whole difference again when only one character has changed. \n\nIn other words, as we slide the window, all that we are doing is just check the one extra character that we added at the end and also before sliding the window remove all the calculations for that character.\n\t\t\nAnd the rest, is a general sliding window template.\n\nYou might be thinking does type-1 operation even helps in minimizing the flips? Because for above example, even if we don\'t do type-1 operation, we get 2 minimum flips. And after doing as well, we get 2.  Yes, you are right. For some strings, this doubling of strings is not required at all. That\'s the case with even number of characters in a given string. So, if length of string is even, there is no need to double the string. But  when there is an odd number, we may get a minimum value after doing type-1 operation. Try with s = "11100" you will understand.\n\nBecause in "11100" if we take four characters from beginning and append them to end we get "01110\' ANd now, all we need to do is 1 flip for the 1 at the center to make it "01010". So minimum Flips = 1\n\nBut had we not done the type-1 operation at all, then minimum flips would be 2. i.e., flipping the 2nd "1" and last "0" to get "10101"\n\n\n```\ndef minFlips(self, s: str) -> int:\n        # Minimum number of flips to return\n        minimumFlips = len(s)\n        \n        # Window Size\n        k = len(s)\n        \n        # For strings of odd length, double them\n        # So that we do not have to manually perform type-1 operation \n        # that is, taking each bit and moving to end of string\n        s = s if k % 2 == 0 else s + s\n        \n        # There can be only two valid alternating strings as we only have 0 and 1\n        # One starts with 0 and other with 1\n        # e.g. for a string of length 3 we can have either 010 or 101\n        altArr1, altArr2 = [], []        \n        for i in range(len(s)):\n            altArr1.append("0" if i % 2 == 0 else "1")\n            altArr2.append("1" if i % 2 == 0 else "0")\n            \n        alt1 = "".join(altArr1)\n        alt2 = "".join(altArr2)\n        \n        \n        # Minimum Number of operations = Minimum Difference between the string and alt2 and alt3\n        diff1, diff2 = 0,0\n        \n        # Sliding Window Template Begins\n        i,j = 0,0\n        \n        \n        while j < len(s):\n            if s[j] != alt1[j] : diff1 += 1\n            if s[j] != alt2[j] : diff2 += 1\n                \n            if j - i + 1 < k: j += 1\n            else:\n                minimumFlips = min(minimumFlips, diff1, diff2)\n                if s[i] != alt1[i] : diff1 -= 1\n                if s[i] != alt2[i] : diff2 -= 1\n                i += 1\n                j += 1\n        \n        return minimumFlips\n```
['Sliding Window', 'Python']