<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:
        def valid(a, c) -> bool:
            return abs(ord(a)-ord(c)) <= 2
        def all_equal_to(counter, k):
            for _, v in counter.items():
                if v not in (0,k):
                    return False
            return True
        def has_any_less_than(counter, k):
            for _, v in counter.items():
                if 0 < v < k:
                    return True
            return False

        def count_item_from_start(s, counters):
            if len(s) < k:
                return 0
            end_pos = len(s) - 1
            if counters[s[0]] < k:
                return 0
            elif counters[s[0]] > k:
                while counters[s[0]] > k:
                    counters[s[end_pos]] -= 1
                    end_pos -= 1
            
            cnt = 0
            while counters[s[0]] == k:
                if all_equal_to(counters, k):
                    cnt += 1
                counters[s[end_pos]] -= 1
                end_pos -= 1
            #print(f'{s[0:10]}-{len(s)} ==> {cnt}')
            return cnt

        def count_fix_length(s, length):
            if len(s) < length:
                return 0
            p = length
            counter = Counter(s[0:length])
            cnt = 0

            if all_equal_to(counter, k):
                cnt += 1
            while p < len(s) :
                counter[s[p-length]] -=1
                counter[s[p]] += 1
                p+= 1
                if all_equal_to(counter, k):
                    cnt += 1
            #print(f'{s} * {length} => {cnt}')
            return cnt
        def count_item(s):
            cnt = 0
            for i in range(1, 27):
                cnt += count_fix_length(s, i * k)
            return cnt

        start = 0
        end = 1
        words = []
        while True:
            while end < len(word) and valid(word[end-1], word[end]):
                end += 1
            words.append(word[start:end])
            if end >= len(word):
                break
            start = end
            end = start+1
        #print (words)

        return sum([count_item(item) for item in words])


5006