How to Find the Most Frequent Substring with Length Constraints – LeetCode 1297 Solution

Problem Statement

Given a string s and integers maxLetters, minSize, maxSize, return the maximum number of occurrences of any substring that satisfies two conditions: the substring contains at most maxLetters distinct characters, and its length is between minSize and maxSize inclusive.

Key Insight

Because any longer substring necessarily contains a shorter one, the optimal substring length can be limited to minSize. Therefore the problem reduces to a fixed‑size sliding‑window of length minSize.

Algorithm

Maintain a sliding window of size minSize. While moving the window, keep an array alphaCnt[128] to count character frequencies and a variable difCnt for the number of distinct characters in the current window. When the window size reaches minSize, if difCnt ≤ maxLetters the current substring is valid; record it in a hashmap mp that maps substrings to their occurrence counts, and update the answer with the highest count. Then slide the window forward by removing the leftmost character and adjusting difCnt accordingly.

Complexity

Time: O(n), where n = s.length(), each character is processed a constant number of times.

Space: O(n) for the hashmap storing all distinct valid substrings (worst case).

Reference Implementation (Java)

public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
    int ans = 0, n = s.length();
    int difCnt = 0;
    int left = 0, right = 0;
    int[] alphaCnt = new int[128];
    Map<String, Integer> mp = new HashMap<>();
    while (right < n) {
        if (alphaCnt[s.charAt(right++)]++ == 0) difCnt++;
        if (right - left == minSize) {
            if (difCnt <= maxLetters) {
                String str = s.substring(left, right);
                int freq = mp.getOrDefault(str, 0);
                mp.put(str, freq + 1);
                ans = Math.max(ans, freq + 1);
            }
            if (alphaCnt[s.charAt(left++)]-- == 1) difCnt--;
        }
    }
    return ans;
}

Reference Implementation (C++)

int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
    int ans = 0, n = s.length();
    int difCnt = 0;
    int left = 0, right = 0;
    vector<int> alphaCnt(128, 0);
    unordered_map<string, int> mp;
    while (right < n) {
        if (alphaCnt[s[right++]]++ == 0) difCnt++;
        if (right - left == minSize) {
            if (difCnt <= maxLetters) {
                string str = s.substr(left, minSize);
                mp[str]++;
                ans = max(ans, mp[str]);
            }
            if (alphaCnt[s[left++]]-- == 1) difCnt--;
        }
    }
    return ans;
}