<p>You are given a string <code>word</code> and an integer <code>k</code>.</p>

<p>A substring <code>s</code> of <code>word</code> is <strong>complete</strong> if:</p>

<ul>
	<li>Each character in <code>s</code> occurs <strong>exactly</strong> <code>k</code> times.</li>
	<li>The difference between two adjacent characters is <strong>at most</strong> <code>2</code>. That is, for any two adjacent characters <code>c1</code> and <code>c2</code> in <code>s</code>, the absolute difference in their positions in the alphabet is <strong>at most</strong> <code>2</code>.</li>
</ul>

<p>Return <em>the number of <strong>complete </strong>substrings of</em> <code>word</code>.</p>

<p>A <strong>substring</strong> is a <strong>non-empty</strong> contiguous sequence of characters in a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;igigee&quot;, k = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> The complete substrings where each character appears exactly twice and the difference between adjacent characters is at most 2 are: <u><strong>igig</strong></u>ee, igig<u><strong>ee</strong></u>, <u><strong>igigee</strong></u>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> word = &quot;aaabbbccc&quot;, k = 3
<strong>Output:</strong> 6
<strong>Explanation:</strong> The complete substrings where each character appears exactly three times and the difference between adjacent characters is at most 2 are: <strong><u>aaa</u></strong>bbbccc, aaa<u><strong>bbb</strong></u>ccc, aaabbb<u><strong>ccc</strong></u>, <strong><u>aaabbb</u></strong>ccc, aaa<u><strong>bbbccc</strong></u>, <u><strong>aaabbbccc</strong></u>.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= word.length &lt;= 10<sup>5</sup></code></li>
	<li><code>word</code> consists only of lowercase English letters.</li>
	<li><code>1 &lt;= k &lt;= word.length</code></li>
</ul>

class Solution:
  def countCompleteSubstrings(self, word: str, k: int) -> int:
    class MyWindow(SlidingWindow):
      def __init__(self):
        super().__init__(word, InvertedIndex())

      def should_contract_left(self, li: int, ri: int) -> bool:
        return len(self.observer.map[word[ri]]) > k

      def is_window_good(self, li: int, ri: int) -> bool:
        return True

    def diff(c1, c2):
      return abs(ord(c1) - ord(c2))

    cutpoints = [i for i in range(1, len(word)) if diff(word[i-1], word[i]) > 2] + [len(word)]

    result = 0
    win = MyWindow()
    inv_idx = win.observer.map
    prev_i = 0
    for i in cutpoints:
      for _, ri in win.run(range(prev_i, i)):
        candidates = sorted((inv_idx[c][0] for c in inv_idx if len(inv_idx[c]) == k), reverse=True)
        result += sum(1 for j, li in enumerate(candidates) if ri - li + 1 == (j + 1) * k) 
      prev_i = i
    return result


from collections.abc import Sequence


class SlidingWindow:
  """Represents a sliding window algorithm framework.

  This class provides a structure for implementing sliding window algorithms.
  Concrete implementations should inherit from this class and override the
  should_contract_left() and is_window_good() methods.
  """

  class Observer:

    def init(self, sequence: Sequence):
      self.seq = sequence

    def start_run(self, _range):
      ...

    def finish_run(self):
      ...

    def enter_cell(self, right_idx: int):
      ...

    def exit_cell(self, left_idx: int):
      ...

  def __init__(self, sequence: Sequence, observer=None):
    self.seq = sequence
    self.observer = observer if observer is not None else self.Observer()
    self.observer.init(sequence)

  def should_contract_left(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def is_window_good(self, left_idx: int, right_idx: int) -> bool:
    raise NotImplementedError()

  def run(self, _range=None):
    _range = _range if _range is not None else range(len(self.seq))
    self.observer.start_run(_range)
    li = _range.start
    for ri in _range:
      self.observer.enter_cell(ri)
      while li <= ri and self.should_contract_left(li, ri):
        self.observer.exit_cell(li)
        li += _range.step
      if li <= ri and self.is_window_good(li, ri):
        yield li, ri
    self.observer.finish_run()


class LengthBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_len: int, max_len: int, observer=None):
    super().__init__(sequence, observer)
    self.min_len = min_len
    self.max_len = max_len

  def should_contract_left(self, li: int, ri: int) -> bool:
    return ri - li + 1 > self.max_len

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_len <= ri - li + 1 <= self.max_len


class AggregateBoundSlidingWindow(SlidingWindow):

  def __init__(self, sequence, min_value, max_value, observer=None):
    super().__init__(sequence, observer)
    self.min_value = min_value
    self.max_value = max_value

  def should_contract_left(self, li: int, ri: int) -> bool:
    return self.observer.aggregate() > self.max_value

  def is_window_good(self, li: int, ri: int) -> bool:
    return self.min_value <= self.observer.aggregate() <= self.max_value


class Count(SlidingWindow.Observer):

  def __init__(self):
    from collections import Counter
    self.counter = Counter()

  def start_run(self, _range):
    self.counter.clear()

  def enter_cell(self, ri):
    self.counter[self.seq[ri]] += 1

  def exit_cell(self, li):
    val = self.seq[li]
    self.counter[val] -= 1
    if self.counter[val] == 0:
      del self.counter[val]


class InvertedIndex(SlidingWindow.Observer):

  def __init__(self):
    from collections import defaultdict, deque
    self.map = defaultdict(deque)

  def start_run(self, _range):
    self.map.clear()

  def enter_cell(self, ri):
    self.map[self.seq[ri]].append(ri)

  def exit_cell(self, li):
    self.map[self.seq[li]].popleft()

class Min(SlidingWindow.Observer):

  def __init__(self):
    from collections import deque
    self._queue = deque()

  def start_run(self, _range):
    self._queue.clear()

  def enter_cell(self, ri: int):
    while self._queue and self.seq[self._queue[-1]] > self.seq[ri]:
      self._queue.pop()
    self._queue.append(ri)

  def exit_cell(self, li: int):
    while self._queue and self._queue[0] <= li:
      self._queue.popleft()

  def min(self):
    return self.seq[self.min_idx()]

  def min_idx(self):
    assert self._queue
    return self._queue[0]


class Sort(SlidingWindow.Observer):

  def __init__(self):
    from sortedcontainers import SortedList
    self.elements = SortedList()

  def start_run(self, _range):
    self.elements.clear()

  def enter_cell(self, ri: int):
    self.elements.add(self.seq[ri])

  def exit_cell(self, li: int):
    self.elements.remove(self.seq[li])


class Sum(SlidingWindow.Observer):

  def __init__(self):
    self.sum = 0

  def start_run(self, _range):
    self.sum = 0

  def enter_cell(self, ri: int):
    self.sum += self.seq[ri]

  def exit_cell(self, li: int):
    self.sum -= self.seq[li]

  def aggregate(self):
    return self.sum
2550