5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4018,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1b:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:Tb5c,

Problem

Given a string s, return the maximum number of ocurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Examples

Example 1:

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).

Example 2:

Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.

Solution

Method 1 - Use Dictionary for counting

Code

[{"language":"Java","code":"class Solution {\n    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {\n        HashMap<String, Integer> count = new HashMap<>();\n        int ans = 0;\n\n        for (int i = 0; i <= s.length() - minSize; i++) {\n            String sub = s.substring(i, i + minSize);\n            if (uniqueChars(sub) <= maxLetters) {\n                count.put(sub, count.getOrDefault(sub, 0) + 1);\n                ans = Math.max(ans, count.get(sub));\n            }\n        }\n\n        return ans;\n    }\n\n    private int uniqueChars(String s) {\n        boolean[] chars = new boolean[26];\n        int uniqueCount = 0;\n\n        for (char c : s.toCharArray()) {\n            if (!chars[c - 'a']) {\n                chars[c - 'a'] = true;\n                uniqueCount++;\n            }\n        }\n\n        return uniqueCount;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:\n        count: defaultdict[str, int] = defaultdict(int)\n        ans: int = 0\n        \n        for i in range(len(s) - minSize + 1):\n            sub: str = s[i:i + minSize]\n            if self.uniqueChars(sub) <= maxLetters:\n                count[sub] += 1\n                ans = max(ans, count[sub])\n        \n        return ans\n\n    def uniqueChars(self, s: str) -> int:\n        return len(set(s))","lang":"python"}]

Complexity

⏰ Time complexity: O(n * (M - m + 1)), where n is the length of the string s, M is maxSize and m is minSize
🧺 Space complexity: O(n), accounting for the hashmap storing substring frequencies.

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wrap items-start justif

Related Tags