[Python] Short and fast solution ignoring maxSize with explanation - O(n) time and space
Every valid substring of length minSize has to occur at least as often as any substring with the same prefix and a higher length. Therefore maxSize can be ignor
Every valid substring of length minSize has to occur at least as often as any substring with the same prefix and a higher length. Therefore maxSize can be ignored.\nYou just need to count the occurence of every valid substring of length minSize and return the maximum count.\n\nTime complexity: ```O(n * minSize) = O(n * 26) = O(n)```\nSpace complexity: ```O(n)```\n\n```python\nclass Solution:\n    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n        n = len(s)\n        substringCount = collections.defaultdict(int)\n        \n        for index in range(n - minSize + 1):\n            substring = s[index:index + minSize]\n            \n            if len(set(substring)) <= maxLetters:\n                substringCount[substring] += 1\n        \n        return max(substringCount.values(), default=0)\n```\n\n**Sliding window using rolling hashes**\n\nJust for fun I decided to implement a sliding window solution. To make it a little more interesting I am using rolling hashes here. Therefore this solution would run in O(n) even if minSize was not limited to 26. The hashes are mod 10^9 + 7 to prevent getting in to big integer sizes. It is basically just adding the current letter to the hash code, letter count and unique letters and removing the starting letter from each of those if the minimum size has been exceeded.\n\nWhile the first solution runs in about 128 ms this one has a lot of practical overhead and completes in about 260 ms.\n\nTime complexity: ```O(n)```\nSpace complexity: ```O(n)```\n\n```python\nclass Solution:\n    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n        n = len(s)\n        modVal = 10**9 + 7\n        hashCount = collections.defaultdict(int)\n        letterCount = collections.defaultdict(int)\n        uniqueLetters = set()\n        hashCode = 0\n        \n        for index in range(n):\n            addLetter = s[index]\n            letterCount[addLetter] += 1\n            uniqueLetters.add(addLetter)\n            hashCode = (hashCode * 26 + ord(addLetter) - 97) % modVal\n            \n            if index + 1 < minSize:\n                continue\n                \n            if len(uniqueLetters) <= maxLetters:\n                hashCount[hashCode] += 1\n            \n            removeLetter = s[index - minSize + 1]\n            hashCode -= ((ord(removeLetter) - 97) * (26 ** (minSize - 1))) % modVal\n            letterCount[removeLetter] -= 1\n            \n            if not letterCount[removeLetter]:\n                uniqueLetters.remove(removeLetter)\n        \n        return max(hashCount.values(), default=0)\n```
['Sliding Window', 'Rolling Hash', 'Python3']