Python: very bad description of the problem. With explanation
Intuition\nThe problem has a terrible description. For a very long period of time I thought that the question asks what it asks: return the number of substrings
# Intuition\n**The problem has a terrible description**. For a very long period of time I thought that the question asks what it asks: return the number of substrings.\n\nSo basically for `countCompleteSubstrings("aaaaaaaaaaaaaaa", 3)` it should return `1` as the only substring you can achieve is `aaa`. You can find that string at 13 different positions but it is still the same string. And spent a lot of time trying to come up with this algorithm. Also seeing that only a few people were able to solve it only reinforced this idea.\n\nSomewhere at the end of the competition I thought to try a simpler question which asks for unique positions (what will return 13 in the above example) and it worked. Yes, I solved the problem but could have done it way faster with a normal explanation. So when you create a question, either explain exactly what you want people to do or give not-trivial test-cases.\n\n------------------\nNow rant is over and we know what we want to do so we are back to the question. You can easily decompose the problem into two problems:\n\n 1. Find a group of characters where the difference between two adjacent characters is at most 2.\n 2. And then for each such group check how many substrings it has where each character occurs exactly k times.\n\nSo solve problem 1, see the part part in `countCompleteSubstrings` where I create groups. For problem 2 see `count_substrings`\n\n# Complexity\n\nLet $d$ be the size of the alphabet. In our case it is 26\n\n- Time complexity: $O(n * d) = O(n)$\n- Space complexity: $O(d) = O(1)$\n\n# Code\n```\nclass Solution:\n\n  def is_same_frequency(self, freq, k: int):\n    return all([freq[i] == k or freq[i] == 0 for i in freq])\n\n  def count_substrings(self, s: str, k: int) -> int:\n    count, distinct = 0, len(set([i for i in s]))\n\n    for l in range(1, distinct + 1):\n      max_l, freq = l * k, defaultdict(int)\n      pos_s, pos_e = 0, max_l - 1\n\n      for i in range(pos_s, min(pos_e + 1, len(s))):\n        freq[s[i]] += 1\n\n      while pos_e < len(s):\n        if self.is_same_frequency(freq, k):\n          count += 1\n\n        freq[s[pos_s]] -= 1\n        pos_s, pos_e = pos_s + 1, pos_e + 1\n        if pos_e < len(s):\n          freq[s[pos_e]] += 1\n    return count\n\n  def countCompleteSubstrings(self, word: str, k: int) -> int:\n    groups = [[]]\n    for c in word:\n      if len(groups[-1]) == 0:\n        groups[-1].append(c)\n      elif abs(ord(groups[-1][-1]) - ord(c)) <= 2:\n        groups[-1].append(c)\n      else:\n        groups.append([c])\n\n    res = 0\n    for g in groups:\n      res += self.count_substrings(\'\'.join(g), k)\n\n    return res\n```
['Python3']