DETAILED EXPLANATION | SLIDING WINDOW | JAVA
Sliding Window\nGiven: 1011010\nif only type-2 op is there, 1 op = fliping any one bit\nWe have to make the given string alternating.\nThere are only two possib
# Sliding Window\nGiven: 1011010\nif only type-2 op is there, 1 op = fliping any one bit\nWe have to make the given string alternating.\nThere are only two possible target - one which starts from 0 and one which starts from 1\nTo tell number of ops to convert the given string to either of these string is to count individual bits which are different\n\nPossible targets -\n0101010 (case 1)\nor\n1010101 (case 2)\n\n## Case 1\n1011010\n0101010\nDiffs = 3, so it requires 3 ops (type-2) to convert the given string to an alternating string which starts from 0\n\nSimilary we do for another possible target-\n## Case 2\n1011010\n1010101\nDiffs = 4, so it requires 4 ops to convert.\n\nSo we can take minimum of these diff counts and say we found the ans.\nBut we are also given TYPE-1 operation. And it says that we can remove character/Bit from start and append it\nto the end of the given string. And this Type-1 op doesnt cost anything to us. Its a free op and we can do it\nany number of times.\nExample-\nGiven: 1011010\nDo type-1 op -\n0110101\nNow do the same diff count for two possible targets and calculate min.\n```text\n1011010 -> original string\n0110101\n1101010\n1010101\n0101011\n1010110\n0101101\n1011010 -> same as original\n```\nSo after every 7th (nth operation) type-1 ops we will return back to our original string\nFrom this it is clear that for any given string, we can get maximum (n-1) different considerable strings.\nInstead of adding and removing chars to generate the above possible substring\nWe can instead do this in a smart way-\n- Append the same string with itself (string size now becomes 2*n)\n- To get every possible string, just fix a window of size 7 (n) and \n   slide it till the end to get all the possible strings 7 windows (2n-k+1 windows, where k is our window size)\n\n```text\n10110101011010\n_______      \n _______     \n  _______    \n   _______    \n    _______  \n     _______ \n      _______\n       _______\n```\n- But theres one more optimization we need to make.\n   lets say we have "m" windows to statisfy. For each window, we need to count the diffs. \n   And for counting those diffs we were comparing the individual bits with our possible targets\n   So that will cost us $$O(2*n)$$ TC for each window. Giving us an upper bound of $$O(m*n)$$.\n- Can we do better than that?\n   YES.\n   We can apply similar techniques to our possible targets as well by extending it.\n   Take an example -\n   Here we have alternating binary string starting with 0 and 1\n   0101010 (with length of 7 as our given string size)\n   1010101\n   For the first window - 1011010\n   We will count the diffs between for both the target strings.\n   and when our window slides to the right. \n   Our window becomes - 0110101\n   Similarly slide the target strings as well\n   1010101 (our initial target string which was started from 0, now has started from 1)\n   0101010 (our initial target string which was started from 1, now has started from 0)\n   now we count the diffs here again.\n   Similary for all the windows.\n\n   So the conclusion is to also create the target strings with size double of s (i.e 14 here).\n>    Now just slide the window and keep count of diffs for both the targets.\n   **When we move our window towards right - we might need to update(reduce) the count**\n   On moving window to right, your target windows are also changing meaining - removing the bits of one of the target for which you **might** have previously counted as diff\n   Since now you are removing it. That diff dont exists anymore. Meaning - reducing the diff for that target\n\n\nOutput:\n```\nGiven string: 1011010\n0101010\n1010101\ndiffZero: 3, diffOne: 4\n#########\n0110101\n1010101\n0101010\ndiffZero: 2, diffOne: 5\n#########\n1101010\n0101010\n1010101\ndiffZero: 1, diffOne: 6\n#########\n1010101\n1010101\n0101010\ndiffZero: 0, diffOne: 7\n#########\n0101011\n0101010\n1010101\ndiffZero: 1, diffOne: 6\n#########\n1010110\n1010101\n0101010\ndiffZero: 2, diffOne: 5\n#########\n0101101\n0101010\n1010101\ndiffZero: 3, diffOne: 4\n#########\n1011010\n1010101\n0101010\ndiffZero: 4, diffOne: 3\n#########\n```\nFrom the above the ans is 0. \nAs after doing type-1 op 3 times. Our given string transforms to 1010101, which is already alternating.\n\n# Complexity\n- Time complexity: $$O(n)$$ (ignoring any constant)\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\n    public int flip(int i){\n        return i==1?0:1;\n    }\n    public String[] getAlternatingStrings(int n){\n        // create an alternating string of size n+1 which starts with 0\n        // slice from [1,n] and get the alternating string that starts with 1\n        StringBuilder sb = new StringBuilder(); \n        int bit = 0;\n        for(int i=0;i<=n;i++){\n            sb.append(bit);\n            bit = flip(bit);\n        }\n        return new String[]{sb.substring(0, n), sb.substring(1, n+1)};\n    }\n    public int minFlips(String s) {\n        int n = s.length();\n        // construct target strings - O(n) each\n        String[] alternatingTargetStrings = getAlternatingStrings(2*n);\n        String zero = alternatingTargetStrings[0], one = alternatingTargetStrings[1];\n        // append s to itself at the end\n        String str = s+s;\n        int diffZero = 0, diffOne = 0, ans = 2*n;\n        int l = 0, r = 0, m = 2*n;\n        // here, window size is n\n        while(r < m){\n            if(r-l+1 < n){\n                char ch = str.charAt(r);\n                if(ch!=zero.charAt(r)){\n                    diffZero++;\n                }\n                if(ch!=one.charAt(r)){\n                    diffOne++;\n                }\n                r++;\n            }else{\n                // ws is exactly n\n                char rightCh = str.charAt(r);\n                if(rightCh!=zero.charAt(r)){\n                    diffZero++;\n                }\n                if(rightCh!=one.charAt(r)){\n                    diffOne++;\n                }\n                ans = Math.min(ans, Math.min(diffZero, diffOne));\n                // move window to right\n                char leftCh = str.charAt(l);\n                if(leftCh!=zero.charAt(l)){\n                    diffZero--;\n                }\n                if(leftCh!=one.charAt(l)){\n                    diffOne--;\n                }\n                l++; r++;\n            }\n        }\n        return ans;\n    }\n}\n```
['Sliding Window', 'Java']