Count Complete Substrings
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires counting complete substrings in a given string, where a substring 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires counting complete substrings in a given string, where a substring is considered complete if each character in the substring appears exactly k times, and the difference between adjacent characters is at most 2.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDefine a helper method is_same_frequency to check if the frequencies of characters in a substring are either k or 0.\nImplement a method count_substrings to count the number of complete substrings of length l*k for each l from 1 to the number of distinct characters in the string.\nIterate over the groups of characters with adjacent positions differing by at most 2. For each group, count the complete substrings formed by combining characters within the group using the count_substrings method.\nSum up the counts of complete substrings for all groups.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity: O(n^2), where n is the length of the input string. This complexity arises due to nested loops iterating over the string and its substrings.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity: O(n), where n is the length of the input string. The space complexity is dominated by the storage of groups formed from the input string.\n\n# Code\n```\nclass Solution:\n  def is_same_frequency(self, freq, k: int):\n    return all([freq[i] == k or freq[i] == 0 for i in freq])\n  def count_substrings(self, s: str, k: int) -> int:\n    count, distinct = 0, len(set([i for i in s]))\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      for i in range(pos_s, min(pos_e + 1, len(s))):\n        freq[s[i]] += 1\n      while pos_e < len(s):\n        if self.is_same_frequency(freq, k):\n          count += 1\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  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    res = 0\n    for g in groups:\n      res += self.count_substrings(\'\'.join(g), k)\n    return res\n```
['Python3']