1297. Maximum Number of Occurrences of a Substring

1297. Maximum Number of Occurrences of a Substring

Medium

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.

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.

class Solution {
public:
    unordered_map<string, int> hash;
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {

        int res = 0;
        for(int i=minSize; i<=minSize; ++i) {  // only minSize !!!
            res = max(res, maxFreqFixSize(s, maxLetters, i));
        }
        return res;
    }

    int maxFreqFixSize(const string &s, int maxLetters, int fixSize) {
        int res = 0;
        for(int i=0; i+fixSize<=s.size(); ++i) {
            string sub = s.substr(i, fixSize);
            unordered_set<char> uniq(sub.begin(), sub.end());
            if(hash.count(sub)>0 || uniq.size()<=maxLetters) {
                hash[sub]++;
                res = max(res, hash[sub]);
            }
        }
        return res;
    }
};