Python O(n)  time using Trie.
\n\n----\n\nMany people claim their algorithm have O(n) time complexity, while in reality they also calculate substrings which makes their overall time complexi
\n\n----\n\n<del>Many people claim their algorithm have `O(n)` time complexity, while in reality they also calculate substrings which makes their overall time complexity to be `O(n, minSize)`.</del> The following algorithm is also `O(n, minSize)` in time, but uses a trie to track substrings.\n\n(**Update:** the input limit is `minSize <= min(26, s.length)`, so people are right, `O(n * minSize) ~ O(26 n) ~ O(n)`.)\n\nEach item in the `data` array is `[ponter_to_a_trie_node, visited_letters_set]`.\n\nImagine starting from each letter of `s` to scan the substrings simultaneously, at the same speed. If two substrings are same, then their `ponter_to_a_trie_node` will point to the same trie node.\n\n```\nimport collections\nclass Solution(object):\n    def maxFreq(self, s, maxLetters, minSize, maxSize):\n        T = lambda: collections.defaultdict(T)\n        trie = T()\n        data = [[trie, set()] for _ in xrange(len(s))]\n        res = 0\n        for l in xrange(minSize):\n            for start in xrange(len(s)):\n                index = start + l\n                if index == len(s):\n                    break\n                this_data = data[start]\n                c = s[index]\n                this_data[1].add(c)\n                if len(this_data[1]) <= maxLetters and l == minSize - 1:\n                    this_data[0][c].setdefault("#", 0)\n                    this_data[0][c]["#"] += 1\n                    res = max(res, this_data[0][c]["#"])\n                this_data[0] = this_data[0][c]\n        return res\n```\n\n---\n\nAlso, a python 2-line solution:\nhttps://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457792/Python-O(n)-2-line
[]