C++ O(n) Sliding Window Solution with Explanation
We solve this problem in O(n) time by making use of the key observation that a substring of maximum occurance must necessarily be of minSize length. This can ea
We solve this problem in O(n) time by making use of the key observation that **a substring of maximum occurance must necessarily be of minSize length**. This can easily be proved by contradiction. If a result were larger in length it must share the first minSize characters and therefore, our observation.\n\nSo, we only observe substrings of length minSize. At each window, we update our character counts **(incrementing char_count[right] and decrementing char_count[right - minSize])** and check if the size of the character map is within the maxLetters limit. If yes, we increment the count of the current substring. Finally, we return the count of the most frequently seen window.\n\n```\nclass Solution {\npublic:\n    unordered_map<int, int> char_count;\n    map<string, int> substr_count;\n    \n    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {\n        if(minSize > s.length())\n            return 0;\n        int result = 0;\n        for(int i = 0; i < minSize; i++) {\n            char_count[s[i]]++;\n        }\n        \n        //  Check the inital window [0, minSize].\n        if(char_count.size() <= maxLetters) {\n            substr_count[s.substr(0, minSize)]++;\n            result = max(result, substr_count[s.substr(0, minSize)]);\n        }\n        for(int right = minSize; right < s.length(); right++) {\n            /*\n                At each iteration, add a new character S[right] and remove the\n                leftmost (S[right - minSize], keeping window size at minSize at\n                all times.\n            */\n            char_count[s[right - minSize]]--;\n            if(char_count[s[right - minSize]] == 0)\n                char_count.erase(s[right - minSize]);            \n            char_count[s[right]]++;\n            \n            // Check if window satisfies maxLetters condition.\n            if(char_count.size() <= maxLetters) {\n                substr_count[s.substr(right - minSize + 1, minSize)]++;\n                result = max(result, substr_count[s.substr(right - minSize + 1, minSize)]);\n            }\n        }\n        return result;\n    }\n};\n```
['Hash Table', 'C', 'Sliding Window']