C++ Sliding Window Solution O(N)
Runtime: 36 ms, faster than 95.83% of C++ online submissions for Maximum Number of Occurrences of a Substring.\nMemory Usage: 13.2 MB, less than 91.33% of C++ o
Runtime: 36 ms, faster than 95.83% of C++ online submissions for Maximum Number of Occurrences of a Substring.\nMemory Usage: 13.2 MB, less than 91.33% of C++ online submissions for Maximum Number of Occurrences of a Substring.\n\n\n```\nMax occuerence of substring with given criteria can be solved using Sliding Window approach.\nHere substring length can be between minSize adn maxSize, hence maxSize can be ignored as \nthe minSize substring occuerence will be same as the maxSize substring occurence and so we\nonly impose the condition of substring length == minSize. For tracking multiple occuerence of\nsubstring we use hash map. Shrink window if unique char count > maxLetters or window length > minSize.\n```\n\n```\nclass Solution {\npublic:\n    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {\n        \n        int n = s.length();\n        \n        // track the substring count\n        unordered_map<string,int>track;\n        \n        // count the unique chars in the window\n        int unique_count = 0;\n        \n        // char freq count \n        int freq_count[26] = {0};\n        \n        // first and last pointer of the window\n        int first = 0;\n        int last  = 0;\n        \n        // max number of substring with given condition\n        int result = 0;\n        while(last < n)\n        {\n            // increment freq of char and unique char if new char in the window\n            if(++freq_count[s[last++]-\'a\']==1)unique_count++;\n            \n            // check if window has uqnique char count > maxLetters and window size > minSize\n            // then shrink window by incrementing first and updating freq count and unique char count\n            while(unique_count > maxLetters || (last-first) > minSize)\n                if(--freq_count[s[first++]-\'a\']==0)--unique_count;\n            \n            // valid condition is current window has length == minSize and so update result\n            if((last-first) == minSize)\n                result = max(result,++track[s.substr(first,minSize)]);\n        }\n        \n        return result;\n    }\n};\n```
['String', 'C', 'Sliding Window']