Python: TLE or not TLE
it looks medium, but with the runtime restrictions it\'s real pain in one place.\n\nCount all valid windows of size unique_chars * k with c[i - 1] - c[i] <= 2\n
it looks **medium**, but with the runtime restrictions it\'s real pain in one place.\n\nCount all **valid** windows of size **unique_chars * k with c[i - 1] - c[i] <= 2**\n\nTC: O(26*N)\nSC: O(26)\n\n> defaultdict: 5.9 sec\n```\nclass Solution:\n    def countCompleteSubstrings(self, word: str, k: int) -> int:\n        N = len(word)\n        count = 0\n        for unique_chars in range(1, 26 + 1):\n            if unique_chars * k > N: # this is the fix for TLE in my case (now ~6 sec)\n                break\n            freq = defaultdict(int)\n            window_size = unique_chars * k\n            left = 0\n            k_times_chars = 0\n            for right in range(N):\n                freq[word[right]] += 1\n                if right and abs(ord(word[right]) - ord(word[right - 1])) > 2:\n                    freq = defaultdict(int)\n                    freq[word[right]] += 1\n                    k_times_chars = 0\n                    left = right\n                if freq[word[right]] == k:\n                    k_times_chars += 1\n                if right - left + 1 >= window_size:\n                    count += k_times_chars * k == window_size\n                    if freq[word[left]] == k:\n                        k_times_chars -= 1\n                    freq[word[left]] -= 1\n                    left += 1\n        return count\n```\n> array: 5.8\n```\n        N = len(word)\n        count = 0\n        for unique_chars in range(1, 26 + 1):\n            if unique_chars * k > N:\n                break\n            freq = [0] * 26\n            window_size = unique_chars * k\n            left = 0\n            k_times_chars = 0\n            for right in range(N):\n                rightmost_char = ord(word[right]) - ord(\'a\')\n                freq[rightmost_char] += 1\n                if right and abs(ord(word[right]) - ord(word[right - 1])) > 2:\n                    freq = [0] * 26\n                    freq[rightmost_char] += 1\n                    k_times_chars = 0\n                    left = right\n                k_times_chars += freq[rightmost_char] == k\n                if right - left + 1 >= window_size:\n                    leftmost_char = ord(word[left]) - ord(\'a\')\n                    count += k_times_chars * k == window_size\n                    k_times_chars -= freq[leftmost_char] == k\n                    freq[leftmost_char] -= 1\n                    left += 1\n        return count\n```
['Sliding Window', 'Python']