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:

1
2
3
4

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:

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        HashMap<String, Integer> count = new HashMap<>();
        int ans = 0;

        for (int i = 0; i <= s.length() - minSize; i++) {
            String sub = s.substring(i, i + minSize);
            if (uniqueChars(sub) <= maxLetters) {
                count.put(sub, count.getOrDefault(sub, 0) + 1);
                ans = Math.max(ans, count.get(sub));
            }
        }

        return ans;
    }

    private int uniqueChars(String s) {
        boolean[] chars = new boolean[26];
        int uniqueCount = 0;

        for (char c : s.toCharArray()) {
            if (!chars[c - 'a']) {
                chars[c - 'a'] = true;
                uniqueCount++;
            }
        }

        return uniqueCount;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        count: defaultdict[str, int] = defaultdict(int)
        ans: int = 0
        
        for i in range(len(s) - minSize + 1):
            sub: str = s[i:i + minSize]
            if self.uniqueChars(sub) <= maxLetters:
                count[sub] += 1
                ans = max(ans, count[sub])
        
        return ans

    def uniqueChars(self, s: str) -> int:
        return len(set(s))

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.