DETAILED explanation of algo and easy to understand O(n) python code with comments
This is a DP solution. O(n) time complexity (two pass solution) and O(n) space complexity.\nthe array dp stores the number of changes you need to make in the st
This is a DP solution. O(n) time complexity (two pass solution) and O(n) space complexity.\nthe array dp stores the number of changes you need to make in the string to get 0101... (not considering 1010... at the moment, Later! See the note below)\nSo, if the string char doesn\'t match with the char in 0101... we add 1 to last element of dp and insert in the dp array, else just copy the previous element of dp.\nif given s is       11011001\ndp will store     11112333 (though the dp array in code will actuallu look like 011112333)\nTo make it easy to code, have added a 0 at the start of dp and removed it later. \n**We do this for the s+s instead of s**\nThis is because instead of the rotaton operation we can just consider it as a cyclic array.\ne.g. \n11011001 ---rotation--> 10110011 --rotation--> 01100111\nInstead of doing this what we do is:\n\t\ts\t\t+\t\ts\n11011001 + 11011001 = 1101100111011001\nIf we consider the first n elements in s+s we get the inital s obviously\nthen we consider n elements from 1st index of s+s , we get the s after 1 rotation\nthen we consider n elements from 2nd index of s+s, we get the s after 2 rotations... and so on, we get our n different strings after n rotations(which would repat after n rotations)\nso now for each of these n strings we just need to check the number of flips required, but that would give an O(n^2) solution, **DP comes to rescue, the dp array is useful here**\n\nfor each window we subtract dp[left_index] from dp[right_index] which I do by the code """val=dp[i]-dp[i%x]""" and that gives us the number of flips required to convert the string to 0101... \nWe can check for 1010 easily! HOW?\n\nNote: If it takes "x" moves to convert a string of length "n" to 1010... then it would take "n-x" moves to convert it to 0101...\nSo, you just need to chcek for one of them and you get by subtracting from the length and the min of the two is the answer.\n\n"""\nclass Solution:\n    def minFlips(self, s: str) -> int:\n        \n        \n        n=len(s)\n        def func(st):                                # st is s+s    e.g. if s = "101"  st = "101101" \n            dp=[0]                                     #0 is appended at start for ease to code\n            x=len(st)//2                             # x is length of s ( st = s + s )\n            for i in range(len(st)):\n                if i%2!=int(st[i]):\n                    dp.append(dp[-1]+1)\n                else:\n                    dp.append(dp[-1])\n            dp.pop(0)\n            maxi=0\n            mini=x+10\n            for i in range(x,2*x):\n                val=dp[i]-dp[i%x]\n                mini=min(mini,val) #storing the min flips required to convert string to 0101....\n\t\t\t\tmaxi=max(maxi,val)  #storing the max flips required to convert string to 0101...   , max steps to 0101... means min steps to 1010... so we storing it for 1010...\n\t\t\t\t\n            return min(mini,x-maxi)\n            \n            \n        return func(s+s)\n"""\nNOTE: This code can be easily optimized to O(1) space once you have understood the logic, (just store the left_index value instead of keeping the whole array and keep finding right_index value as you proceed)\n\nFeel free to ask doubts.
['Dynamic Programming', 'Python', 'Python3']