99% Running time | SLIDING WINDOW | Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the maximum frequency of substrings within given constrain
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the maximum frequency of substrings within given constraints on the number of distinct letters and the substring size. A sliding window approach combined with a frequency dictionary is a suitable way to solve this problem efficiently.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUse a sliding window to track the current substring and a dictionary to count the frequency of each letter. Adjust the window size and the dictionary to ensure the current window meets the constraints: no more than maxLetters distinct letters and the length between minSize and maxSize. Use another dictionary to count the occurrences of valid substrings. Track and return the maximum frequency found.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n) \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution(object):\n    def maxFreq(self, s, maxLetters, minSize, maxSize):\n        """\n        :type s: str\n        :type maxLetters: int\n        :type minSize: int\n        :type maxSize: int\n        :rtype: int\n        """\n        # maxCount <= maxLetters\n        # minSize <=  len(window) <= maxSize\n        # maximum number of occurences = maxCount\n        currWindow, currLen = [], 0\n        letterDict = {}\n        left = 0\n        n = len(s)\n        countMap = {}\n        maxOccur = 0\n        ret = []\n\n        for right in range(n):\n            letter = s[right]\n            currWindow.append(letter)\n            if letter in letterDict:\n                letterDict[letter] += 1\n            else:\n                letterDict[letter] = 1\n            currLen += 1\n\n            while len(letterDict) > maxLetters or currLen > maxSize:\n                removedLetter = s[left]\n                currWindow.remove(removedLetter)\n                currLen -= 1\n                if removedLetter in letterDict:\n                    if letterDict[removedLetter] == 1:\n                        letterDict.pop(removedLetter)\n                    else:\n                        letterDict[removedLetter] -= 1\n                left += 1\n\n            # at this point satisfies the conditions\n            m = len(letterDict)\n            while m <= maxLetters and currLen >= minSize and currLen <= maxSize:\n                joinedString = "".join(currWindow)\n                if joinedString in countMap:\n                    countMap[joinedString] += 1\n                else:\n                    countMap[joinedString] = 1\n                maxOccur = max(maxOccur, countMap[joinedString])\n                removedLetter = s[left]\n                currWindow.remove(removedLetter)\n                currLen -= 1\n                if removedLetter in letterDict:\n                    if letterDict[removedLetter] == 1:\n                        letterDict.pop(removedLetter)\n                    else:\n                        letterDict[removedLetter] -= 1\n                left += 1\n                m = len(letterDict)\n                \n        return maxOccur                    \n```\n\n![packied_spongebob.jpg](https://assets.leetcode.com/users/images/f89c6f75-aabe-40d4-9c91-e39fa5c5422b_1720793857.363409.jpeg)\n
['Sliding Window', 'Python', 'Python3']