[C++] Greedy approach + Sliding window O(n).
Observation\n\nLet\'s assume we have a fixed size of window (minSize), we can easily use a sliding window of that size and check for the contraints within that 
**Observation**\n\nLet\'s assume we have a fixed size of window (`minSize`), we can easily use a sliding window of that size and check for the contraints within that window.\nThis can be done in `O(n)` using a hashmap to store the unique count of letters in the window.\n\nThe greedy part of the solution is that, we also notice that we only need `minSize` since if the `minSize` satisfies the constraints to have `distinct letters <= maxLetters ` any substring greater than that size would only add at max a new distinct letter.\nWhich esentially means that since the substring of size greater than minSize starisfies the constraint of `distinct letters <= maxLetters ` there will be a substring of this selected substring of size minSize that\'ll satisfy the same constraint and the frequency of this substring will be atleast as much as the parent substring.\nWe also know that number of shorter substrings are more than the longer ones , thus we only need to check for substrings of minSize satisfying the condition.\n\nEg: `s=abcabc, minSize=3, maxSize=6, maxLetter=3`\nsubstrings satisfying the constraints are `abc`, `abca` ,`abcab`, `abcabc`, `bca`, `bcab`, `bcabc`, `cab`, `cabc` and `abc` again, we can see that all the substrings have a substring within it of `size=minSize` that satisfies all the conditions, like we have `abc` in first 4 substrings. Thus we only need to check for substrings of `size=minSize` that satisfy the condition to get our result.\n\nThe only problem is that this question ask for the max count of substrings. We can do this in two ways 1 we store the entire sub-string and it\'s count in a hashmap which is an `O(n)` operation (in this case `O(1)` since we can have at max `26` distinct characters) or we can use rolling hash during the sliding window to make it `O(1)`.\n\n**Solution 1**\nThis solution stores substring frequency in hash map which is and `O(n)` operation (`O(26)` `~O(1)` in this case, since this creation and insertion of substring is at most `O(26)`).\n```c++\nclass Solution {\npublic:\n    int maxFreq(string s, int maxLetters, int minSize, int maxSize) \n    {\n        int start=0,result=0;\n        unordered_map<int,int> count;           \t//Stores count of letters in the window.\n        unordered_map<string,int> occurence;        //Stores count of occurence of that string.\n        for(int i=0;i<s.length();i++)\t\t\t//Sliding window\n        {\n            count[s[i]]++;\t\t\t\t\t\t//Increase the count of letter at i.\n            if(i-start+1>minSize)                  //Reduce the size of the window if increased to size.\n            {\n                if(--count[s[start]]==0)\t\t\t//Remove the letter from map if count 0 to track unique letters.\n                    count.erase(s[start]);\n                start++;\n            }\n            if(i-start+1==minSize&&count.size()<=maxLetters)\t//When the substring in the window matches the constraints.\n                result=max(result,++occurence[s.substr(start,i-start+1)]); //Increase the occurence count of the string and get the max.\n        }\n        return result;\n    }\n};\n```\n**Complexity**\nSpace:  `O(26n) = O(n)`. Since `count` can have at max `26` characters and the number of substrings stored in occurence is at max `~n` with at max `26` characters each.\nTime: `O(26n) = O(n)`. Since we create and store the substring in the hashMap which is `O(26)` `~O(1)` operation as the substring length can at max be `26`.\n\n**Solution 2 (Rolling hash)**\nSince, as explained above, in this solution we create hash from substrings and store in the hashmap which is an `O(1)` operation and thus this is an `O(n)` algorithm (explaination below).\nSince the probability of collisions is very less I am avoiding an extra check for collisions, however it can be added to make the solution correct for the remaining cases of collisions.\n```c++\nstatic long MOD=1e9+7;               //Large mod less collisions.\nclass Solution {\npublic:\n    long powMod(long x,int y) {           //Modular power\n        long res=1;\n        while (y>0) \n        { \n            if(y&1) \n                res=(res*x)%MOD; \n            y=y>>1;\n            x=(x*x)%MOD;   \n        } \n        return res; \n    } \n    int maxFreq(string s, int maxLetters, int minSize, int maxSize) \n    {\n        long hash=0,Pow=powMod(53,minSize-1);\n        int start=0,result=0;\n        unordered_map<int,int> count;           \t//Stores count of letters in the window.\n        unordered_map<long,int> occurence;        //Stores count of occurence of that string.\n        for(int i=0;i<s.length();i++)\t\t\t//Sliding window\n        {\n            count[s[i]]++;\t\t\t\t\t\t//Increase the count of letter at i.\n            if(i-start+1>minSize)                  //Reduce the size of the window if increased to size.\n            {\n                hash-=(s[start]-\'a\')*Pow;\n                if(--count[s[start]]==0)\t\t\t//Remove the letter from map if count 0 to track unique letters.\n                    count.erase(s[start]);\n                start++;\n            }\n            hash=(hash*53+s[i]-\'a\')%MOD;\n            if(i-start+1==minSize&&count.size()<=maxLetters)\t//When the substring in the window matches the constraints.\n                result=max(result,++occurence[hash]);     //Increase the occurence count of the string and get max.\n        }\n        return result;\n    }\n};\n```\n**Complexity**\nSpace: `O(n)`. Since `count` can have at max `26` charcters and the number of hashes stored in occurence is at max `~n`.\nTime: `O(n)`. Since we store the string as an integer in the hashMap which is `O(1)` operation.\n
[]