Java/Python/Typescript Sliding window Time Complexity: O(N * minSize) and Space Complexity: O(N)
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\nInput: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4\nOutpu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\nInput: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4\nOutput: 2\n\nHere\'s how the code works:\n\n1. Initialize variables:\n   - `n` is the length of the input string `s`, which is 9 in this case.\n   - `substringFrequency` is a HashMap to store substrings that meet the conditions (i.e., have at most `maxLetters` distinct characters) and their frequencies.\n   - `maxFreq` is a variable to keep track of the maximum frequency of valid substrings. Initialize it to 0.\n\n2. Iterate through the string `s` using a sliding window of size `minSize`. The loop starts at index `i = 0` and goes up to `i = n - minSize`, which ensures that we consider all possible windows of size `minSize`.\n\n3. For each window, extract the substring of length `minSize` starting from index `i`.\n\n   - At the beginning, `i = 0`, so the first window is "aab."\n   - Next, `i = 1`, so the window is "aba," and so on.\n\n4. Within each window, calculate the number of distinct characters by iterating through the characters of the substring.\n\n   - For "aab," there are two distinct characters (\'a\' and \'b\'), which is less than or equal to `maxLetters` (2).\n\n5. If the number of distinct characters in the substring is less than or equal to `maxLetters`, it\'s a valid substring. Increment its frequency in the `substringFrequency` map.\n\n   - For "aab," it becomes: `substringFrequency = {"aab": 1}`\n\n6. Update `maxFreq` if the current substring\'s frequency is greater than the current `maxFreq`.\n\n   - In this case, `maxFreq` remains 0 because the frequency of "aab" is 1.\n\n7. Continue this process for all possible windows of size `minSize`.\n\n- For "aba," it is a valid substring, having less than equal to `maxLetters` distinct characters.\n    -Will increase the SubstringFrequency in hashmap = {"aba": 1}.\n- For "bab," it is a valid substring, having less than equal to `maxLetters` distinct characters.\n    -Will increase the SubstringFrequency in hashmap = {"bab": 1}.\n- For "abc," it\'s also not valid (three distinct characters).\n- For "bca," it\'s also not valid (three distinct characters).\n- For "aab," it is a valid substring, having less than equal to `maxLetters` distinct characters.\n    - Will increase the SubstringFrequency in hashmap = {"aab": 2}.\nThe loop end at this window.\n\n8. For each each window we are updating the frequency if the condition is staisfied.\n\n9. After considering all possible windows, the code returns `maxFreq`, which is 2 in this case.\n\n   - The valid substrings are "aab" with a frequency of 2.\n   - Thus, the maximum frequency is 2.\n\nSo, the output of the code for the given input is indeed 2, as it correctly identifies "aab" and "aab" as valid substrings with the maximum frequency.\n\n# Complexity\n- Time complexity: The time complexity of this code is determined by the following factors:\n\n- Iterating through the string s using a sliding window of size minSize. This loop runs from i = 0 to i = n - minSize, where n is the length of the input string s. The loop iterates once for each window, and each iteration involves extracting a substring and checking the number of distinct characters. Therefore, the time complexity of this part is O(N * minSize), where N is the length of the input string.\n\n- The operations inside the loop, such as extracting substrings, checking the number of distinct characters, and updating the substringFrequency map, all have constant time complexity for each iteration.\n\nOverall, the dominant factor in the time complexity is the first part, which results in a time complexity of O(N * minSize).\n\n- Space complexity: The space complexity of this code is determined by the space used for data structures:\n\n- substringFrequency is a HashMap used to store valid substrings and their frequencies. In the worst case, where all substrings are unique, this map can have up to N entries (one for each substring of length minSize). Therefore, the space complexity for this map is O(N).\n\n- Other variables and data structures used in the code, such as maxFreq, n, and temporary variables, have constant space complexity and do not significantly impact the overall space complexity.\n\n# Code\n**Java**\n```\nclass Solution {\n    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {\n        int n = s.length();\n        Map<String, Integer> substringFrequency = new HashMap<>();\n        int maxFreq = 0;\n\n        for (int i = 0; i <= n - minSize; i++) {\n            String substring = s.substring(i, i + minSize);\n            Set<Character> uniqueChars = new HashSet<>();\n            int distinctChars = 0;\n\n            for (char c : substring.toCharArray()) {\n                if (!uniqueChars.contains(c)) {\n                    distinctChars++;\n                    uniqueChars.add(c);\n                }\n            }\n\n            if (distinctChars <= maxLetters) {\n                int frequency = substringFrequency.getOrDefault(substring, 0) + 1;\n                substringFrequency.put(substring, frequency);\n                maxFreq = Math.max(maxFreq, frequency);\n            }\n        }\n\n        return maxFreq;\n    }\n}\n```\n**Python**\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        n = len(s)\n        substring_frequency = {}\n        max_freq = 0\n        i = 0\n\n        while i <= n - minSize:\n            sub_string = s[i: i + minSize]\n            unique_chars = set()\n            distinct_chars = 0\n\n            for c in sub_string:\n                if c not in unique_chars:\n                    distinct_chars += 1\n                    unique_chars.add(c)\n\n            if distinct_chars <= maxLetters:\n                substring_frequency[sub_string] = substring_frequency.get(sub_string, 0) + 1\n                max_freq = max(max_freq, substring_frequency[sub_string])\n\n            i += 1\n\n        return max_freq\n        \n```\n**TypeScript**\n```\nfunction maxFreq(s: string, maxLetters: number, minSize: number, maxSize: number): number {\n    let n: number = s.length;\n    const substringFrequency: Map<String, number> = new Map();\n    let maxFreq: number = 0;\n\n    for (let i: number = 0; i <= n - minSize; i++) {\n        let substring: String = s.substring(i, i + minSize);\n        let uniqueChars: Set<any> = new Set<any>();\n        let distinctChars: number = 0;\n\n        let final_arr = substring.split(\'\');\n        for (const c of final_arr) {\n            if (!uniqueChars.has(c)) {\n                distinctChars++;\n                uniqueChars.add(c);\n            }\n        }\n\n        if (distinctChars <= maxLetters) {\n            substringFrequency.set(substring, (substringFrequency.get(substring) || 0) + 1);\n            maxFreq = Math.max(maxFreq, substringFrequency.get(substring)!);\n        }\n    }\n\n    return maxFreq;\n}\n```
['Hash Table', 'String', 'Sliding Window', 'Python', 'Java', 'TypeScript']