Problem Description

Given a string s and three integers maxLetters, minSize, and maxSize, find the maximum number of occurrences of any substring of s that meets the following criteria:

• The substring's length is between minSize and maxSize (inclusive).
• The substring contains at most maxLetters unique letters.

Constraints:

• 1 ≤ s.length ≤ 10⁵
• 1 ≤ maxLetters ≤ 26
• 1 ≤ minSize ≤ maxSize ≤ min(26, s.length)
• s consists only of lowercase English letters.

Thought Process

To solve this problem, the initial idea is to check all possible substrings of s that have a length between minSize and maxSize, count their occurrences, and track the maximum. However, this brute-force approach is inefficient because the number of substrings grows rapidly with the length of s.

Upon closer inspection, we can optimize by considering that shorter substrings are more likely to repeat. Therefore, we focus on substrings of length minSize only, since any longer substring will occur less frequently. For each substring, we check if it has at most maxLetters unique characters. We use a hash map to count occurrences efficiently.

By narrowing our search to fixed-length substrings and using a sliding window technique, we can process the string in linear time, making the solution practical even for large inputs.

Solution Approach

The solution involves the following steps:

1. Sliding Window: We use a window of size minSize to iterate through s. At each position, we extract the substring and count its unique characters.
2. Unique Letter Check: For each window, we count how many unique letters are present. If this count is less than or equal to maxLetters, the substring is valid.
3. Counting Occurrences: We use a hash map (dictionary) to count how many times each valid substring appears.
4. Result: After processing all windows, we return the maximum value from the hash map, which represents the most frequent valid substring.

We do not need to consider substrings longer than minSize because any such substring can appear at most as many times as its minSize-length prefix, so the maximum frequency will always be for a substring of length minSize.

Example Walkthrough

Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4

Let's walk through the steps:

1. We slide a window of size 3 across s:
   • Index 0-2: "aab" (unique letters: 2) → valid
   • Index 1-3: "aba" (unique letters: 2) → valid
   • Index 2-4: "bab" (unique letters: 2) → valid
   • Index 3-5: "abc" (unique letters: 3) → invalid
   • Index 4-6: "bca" (unique letters: 3) → invalid
   • Index 5-7: "caa" (unique letters: 2) → valid
   • Index 6-8: "aab" (unique letters: 2) → valid
2. Count occurrences of valid substrings:
   • "aab": 2 times
   • "aba": 1 time
   • "bab": 1 time
   • "caa": 1 time
3. The answer is 2 because "aab" occurs most frequently among valid substrings.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(N^2), where N is the length of s, since all substrings between minSize and maxSize are checked.
• Space Complexity: O(N), for storing all unique substrings.

• Time Complexity: O(N * minSize), as we slide a window of size minSize and count unique letters for each window. Since minSize is at most 26, this is effectively O(N).
• Space Complexity: O(N), for the hash map storing substring counts.

Summary

By focusing on substrings of length minSize and using a sliding window, we drastically reduce the number of substrings to check. A hash map allows us to count occurrences efficiently, and checking unique letters ensures we only consider valid substrings. This approach leverages string properties and hash-based counting to solve the problem elegantly and efficiently.

Code Implementation

from collections import defaultdict

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

#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        unordered_map<string, int> count;
        int n = s.size();
        for (int i = 0; i <= n - minSize; ++i) {
            string sub = s.substr(i, minSize);
            unordered_set<char> unique(sub.begin(), sub.end());
            if (unique.size() <= maxLetters) {
                count[sub]++;
            }
        }
        int res = 0;
        for (auto &p : count) {
            if (p.second > res) res = p.second;
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String, Integer> count = new HashMap<>();
        int n = s.length();
        for (int i = 0; i <= n - minSize; i++) {
            String sub = s.substring(i, i + minSize);
            Set<Character> unique = new HashSet<>();
            for (char c : sub.toCharArray()) unique.add(c);
            if (unique.size() <= maxLetters) {
                count.put(sub, count.getOrDefault(sub, 0) + 1);
            }
        }
        int res = 0;
        for (int val : count.values()) {
            res = Math.max(res, val);
        }
        return res;
    }
}
      

/**
 * @param {string} s
 * @param {number} maxLetters
 * @param {number} minSize
 * @param {number} maxSize
 * @return {number}
 */
var maxFreq = function(s, maxLetters, minSize, maxSize) {
    const count = new Map();
    for (let i = 0; i <= s.length - minSize; i++) {
        const sub = s.substring(i, i + minSize);
        const unique = new Set(sub);
        if (unique.size <= maxLetters) {
            count.set(sub, (count.get(sub) || 0) + 1);
        }
    }
    let res = 0;
    for (let val of count.values()) {
        res = Math.max(res, val);
    }
    return res;
};