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.


&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	1 &lt;= maxLetters &lt;= 26
	1 &lt;= minSize &lt;= maxSize &lt;= min(26, s.length)
	s consists of only lowercase English letters.


#   0   1   2   3
#   a   a   a   a
#   l
#   r

#ref: https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457577/C%2B%2B-Greedy-approach-%2B-Sliding-window-O(n).

#Intuition
#if a string have occurrences x times, any of its substring must also appear at least x times
#there must be a substring of length minSize, that has the most occurrences
#so that we just need to count the occurrences of all substring with length minSize

#Explanation
#find the maximum occurrences of all substrings with length = minSize
class Solution:
    #T=O(n), S=O(n)
    #use sliding window to lock down substrings to minSize limit (greedy approach)
    #then use a counter to count the occurences of valid substrings
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        #dict to store valid substrings and their respective occurences count
        d = defaultdict(int)
        #find longest substrings that has k unique chars
        #counter dict for char count and make sure unique char count is not exceeded
        counter = defaultdict(int)
        #init left and right pointers of sliding window
        r = l = 0
        #iterate right pointer
        while r < len(s):
            counter[s[r]] += 1
            
            #invalid window found, so make it valid again
            #len of window is greater than minSize
            while (r - l + 1) > minSize:
                counter[s[l]] -= 1
                #remove the key from dict for unique char count if it becomes zero
                if counter[s[l]] == 0:
                    del counter[s[l]]
                #increment the left pointer to make it a valid window
                l += 1

            #valid window size (minSize) and unique char count is lesser than or equal to maxLetters
            if r - l + 1 == minSize and len(counter) <= maxLetters:
                #increment count of the occurence of the substring
                d[s[l:r+1]] += 1
            
            #make sure to update right pointer only after an iteration
            r += 1
        
        #return the count of substring with max occurence
        #edge case with no substring
        return max(d.values()) if d else 0
class Solution {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        Map<String,Integer> count = new HashMap<>();
        int ans = 0;
        int n = s.length();
        
        for(int i=0;i+minSize-1<n;i++){
            String y = s.substring(i,i+minSize);
            count.put(y,count.getOrDefault(y,0)+1);

            int unique = uniqueCharactersInString(y);
            if(unique<=maxLetters){
                ans = Math.max(ans,count.get(y));
            }
        }
        //System.out.println(count);
        return ans;
    }
    int uniqueCharactersInString(String y){
        Set<Character> hs = new HashSet<>();
        for(int j=0;j<y.length();j++) 
            hs.add(y.charAt(j));
        return hs.size();
    }
}
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        
        int i, j, k, ans = 0, res, n = s.length();
        
        string temp;
        unordered_map<char, int> st;
        unordered_map<string, int> mp;
        
        i = 0, j = 0;
        while(i <= n - minSize && j < n)
        {
            temp += s[j];
            st[s[j]] += 1;;
            if(temp.length() == minSize)
            {
                if(st.size() <= maxLetters)
                    mp[temp] += 1;
                i += 1;
                st[temp[0]] -= 1;
                if(st[temp[0]] == 0)
                    st.erase(temp[0]);
                temp.erase(temp.begin());
            }
            j += 1;
        }
        for(auto el : mp)
            ans = max(ans, el.second);
        return ans;
    }
};
var maxFreq = function(s, maxLetters, minSize, maxSize) {

    let output = 0;

    let left = 0, right = 0;

    let map = {};

    let map2 = {};

    let count = 0;

    while(right < s.length){

        if(map[s[right]] === undefined){ // adding letters to map to keep track of occurences (count)
            map[s[right]] = 1;
            count++;

        } else {
            if(map[s[right]] === 0){
                count++;
            }
            map[s[right]]++;
        }

        if(right - left + 1 > minSize) { // once over minSize removing occurence of left most letter from map and adjusting count

            map[s[left]]--;
            if(map[s[left]] < 1){
                count--;
            }
            left++;
        }

        if(right - left + 1 >= minSize && count <= maxLetters){
            map2[s.substring(left, right + 1)] = (map2[s.substring(left, right + 1)] || 0) + 1; // if subsitrng meets constraints of size and count add to map2;
        }

        right++;
    }

    Object.entries(map2).map(([key, val]) => output = Math.max(output, val)); // get largest value in map2

    return output;

};
Maximum Number of Occurrences of a Substring