O(N) in Python with Two Point Scan + 26 Queues, beating 97%
Approach\nFor each position $r$, we maintain a window word[l:r+1] that meets the two conditions. Increasing l when either the character word[r] appears more tha
# Approach\nFor each position $r$, we maintain a window `word[l:r+1]` that meets the two conditions. Increasing `l` when either the character `word[r]` appears more than `k` times or distance bewteen `word[r]` and `word[r-1]` more than 2. \nFor each of the 26 alphabets, a deque is used to keep its occurrances in the `word[l:r+1]` window. In this way, we can check if the alphabet appears `k` times in the window. Sort the alphabets appearing `k` times and we can check how many of them are in the rightmost of `word[l:r+1]`.\n\n# Complexity\n- Time complexity: $O(N)$ as the number of alphabets is constant (26).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def countCompleteSubstrings(self, word: str, k: int) -> int:\n        q = defaultdict(deque)\n        l = 0\n        ans = 0\n        for r, c in enumerate(word):\n            q[c].append(r)\n            while (r > 0 and l < r and abs(ord(c) - ord(word[r-1])) > 2) or len(q[c]) > k:\n                q[word[l]].popleft()\n                l += 1\n            candidates = sorted((q[d][0] for d in q if len(q[d]) == k), reverse=True)\n            ans += sum(1 for i, p in enumerate(candidates) if r + 1 - p == k * (i + 1))\n        return ans\n```
['Hash Table', 'Two Pointers', 'Queue', 'Python3']