Python - Fixed Size Sliding Window - MaxSize not Required
You might be thinking - If there is no fixed size given then how is this a fixed size sliding window problem? We only have a range of valid sizes.\n\nWell, we h
You might be thinking - If there is no fixed size given then how is this a fixed size sliding window problem? We only have a range of valid sizes.\n\nWell, we have to figure out the fixed size from the range given.\n\nIn fact, the maxSize is something we will never consider at all! Why? \n\nUnderstand this example -\n\n\t\t\ts = "aaaa", maxLetters = 1, minSize = 3, maxSize = 4\n\t\t\t\n\nLets first see how many substrings are there wth size = maxSize\n\n\tWe have only one i.e., "aaaa" \n\t\nBut if there is 1 substring of size = maxSize, doesn\'t that mean there is at least the same number of substrings of size >= minSize and < maxSize? Since minSize <= maxSize.\n\nAnd indeed there are two substrings with size = minSize\n\n\t"aaa" and "aaa"\n\nIn other words, if we have a substring of size = minSize then it has a bigger possibility of occuring multiple times than a substring that has a larger size. \n\nThe substring with size = minSize will occur either the same number of times as maxSize substring or more than that. So that means, considering maxSize in code is a waste of time. \n\nHere, the lowest limit of size is minSize and that\'s why if we can find a substring of that size, it has a higher chance to occur more than any substring with size > minSize and <= maxSize\n\nThat\'s why, we will only consider substrings of length = minSize and well, we got our fixed Size.\n\nSo we will maintain a window of length = minSize and then for each window check if unique characters are <= maxLetters. If yes, we can consider that substring to be valid and update its count.\n\nIn the end, just pick the highest count and return that.\n\nSo to simplify this problem - \n\n\tGiven a string s, return the maximum number of ocurrences of a substring of size = minSize with at most "maxLetters" unique characters\n\t\nThis means, it is a simple Fixed Size Sliding Window Problem.\n\n```\ndef maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:    \n        # To keep track of uniques\n        dict = {}\n        \n        # To store the valid substrings and number of times they appear\n        substrings = {}\n        \n        \n        i,j = 0,0\n\n        while j < len(s):\n            \n            dict[s[j]] = dict.get(s[j],0) + 1\n            \n            # If window size is not yet minSize, increment j\n            if (j - i + 1) < minSize: j += 1\n            # If window size became minSize, now check the condition for unique letters\n            else:\n                if len(dict) <= maxLetters:\n                    substr = s[i:j+1]\n                    substrings[substr] = substrings.get(substr,0) + 1\n                \n                # Before sliding the window, remove the calculations for ith character\n                dict[s[i]] -= 1\n                if dict[s[i]] == 0: dict.pop(s[i])\n                i += 1\n                j += 1\n        \n        # If substrings dictionary is empty that means we did not find a valid substring as per the rules    \n        # Otherwise, return the maximum count from the dictionary\n        return 0 if not substrings else max(substrings.values())\n```
['Sliding Window', 'Python']