# Count Complete Substrings
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-complete-substrings)
Canonical: https://scaleengineer.com/dsa/problems/count-complete-substrings
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
---
## Problem
You are given a string `word` and an integer `k`.

A substring `s` of `word` is **complete** if:

* Each character in `s` occurs **exactly** `k` times.
* The difference between two adjacent characters is **at most** `2`. That is, for any two adjacent characters `c1` and `c2` in `s`, the absolute difference in their positions in the alphabet is **at most** `2`.

Return _the number of **complete** substrings of_ `word`.

A **substring** is a **non-empty** contiguous sequence of characters in a string.

**Example 1:**

**Input:** word = "igigee", k = 2
**Output:** 3
**Explanation:** The complete substrings where each character appears exactly twice and the difference between adjacent characters is at most 2 are: **igig**ee, igig**ee**, **igigee**.

**Example 2:**

**Input:** word = "aaabbbccc", k = 3
**Output:** 6
**Explanation:** The complete substrings where each character appears exactly three times and the difference between adjacent characters is at most 2 are: **aaa**bbbccc, aaa**bbb**ccc, aaabbb**ccc**, **aaabbb**ccc, aaa**bbbccc**, **aaabbbccc**.

**Constraints:**

* `1 <= word.length <= 105`
* `word` consists only of lowercase English letters.
* `1 <= k <= word.length`

# Approaches
## Brute Force Enumeration
The most straightforward approach is to check every single substring of the given `word`. We can generate all substrings and, for each one, verify if it meets the two conditions for being 'complete': the adjacency character difference and the exact frequency count.
**Time:** O(N^3) - There are O(N^2) substrings. For each substring of average length O(N), we perform a check that takes O(N) time. This results in a total time complexity of O(N^3). · **Space:** O(1) - The space used for the frequency map is constant (size 26).
**Pros:** Simple to understand and implement.; Correct for small input sizes.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints (`N` up to 10^5).
### Explanation
This method involves three nested loops. The first two loops define the boundaries of a substring. The third loop (or loops) is used to validate the substring against the problem's conditions. While simple to conceptualize, its performance is very poor for large inputs.

```java
class Solution {
    public int countCompleteSubstrings(String word, int k) {
        int n = word.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = word.substring(i, j + 1);
                if (isComplete(sub, k)) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isComplete(String s, int k) {
        // Check adjacency condition
        for (int i = 0; i < s.length() - 1; i++) {
            if (Math.abs(s.charAt(i) - s.charAt(i + 1)) > 2) {
                return false;
            }
        }

        // Check frequency condition
        int[] freq = new int[26];
        for (char c : s.toCharArray()) {
            freq[c - 'a']++;
        }

        for (int f : freq) {
            if (f > 0 && f != k) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Initialize a counter for complete substrings to zero.
2. Generate all possible substrings of the input `word` using two nested loops. The outer loop iterates through the starting index `i`, and the inner loop iterates through the ending index `j`.
3. For each substring `s = word.substring(i, j + 1)`:
    a. **Check Adjacency Condition:** Iterate from the first to the second-to-last character of `s`. If `abs(s.charAt(p) - s.charAt(p + 1)) > 2` for any `p`, the substring is not complete. Continue to the next substring.
    b. **Check Frequency Condition:** If the adjacency condition holds, create a frequency map (e.g., an array of size 26) for the characters in `s`.
    c. Iterate through the frequency map. If any character has a frequency that is non-zero but not equal to `k`, the substring is not complete.
    d. If both conditions are satisfied, increment the counter.
4. Return the final count.

## Sliding Window per Starting Position
A significant optimization comes from realizing that the adjacency condition (`abs(c1 - c2) <= 2`) allows us to partition the problem. We can split the `word` into chunks where this condition holds for all adjacent characters. Then, we only need to search for complete substrings within these chunks. For each chunk, we can use a more optimized O(M^2) approach (where M is the chunk length) instead of O(M^3).
**Time:** O(N^2) - In the worst case, the entire string is one large chunk. The two nested loops over the chunk lead to a quadratic time complexity. `sum(M_i^2)` over all chunks can be `O(N^2)`. · **Space:** O(1) - The frequency map requires constant space.
**Pros:** More efficient than the naive brute-force approach.; Correctly utilizes the adjacency property to partition the problem.
**Cons:** The O(N^2) time complexity is still too slow for the problem's constraints and will likely time out.
### Explanation
This approach reduces the problem space by first breaking the string down. Within each valid chunk, we iterate through all possible starting points. For each starting point, we expand a window to the right, character by character, maintaining a frequency count. We can quickly discard invalid windows if any character count surpasses `k`. The check for a complete substring is simplified by comparing the product of distinct characters and `k` with the current window's length.

```java
class Solution {
    public int countCompleteSubstrings(String word, int k) {
        int totalCount = 0;
        int n = word.length();
        int start = 0;
        for (int i = 1; i <= n; i++) {
            if (i == n || Math.abs(word.charAt(i) - word.charAt(i - 1)) > 2) {
                // Process the chunk word.substring(start, i)
                totalCount += countInChunk(word.substring(start, i), k);
                start = i;
            }
        }
        return totalCount;
    }

    private int countInChunk(String s, int k) {
        int count = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            int distinct = 0;
            for (int j = i; j < n; j++) {
                int charIndex = s.charAt(j) - 'a';
                if (freq[charIndex] == 0) {
                    distinct++;
                }
                freq[charIndex]++;

                if (freq[charIndex] > k) {
                    // This window and any larger ones starting at i are invalid
                    break;
                }
                
                if (distinct * k == (j - i + 1)) {
                    // If length is distinct * k, and no freq > k, all must be == k.
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. **Split into Chunks:** First, iterate through the `word` and split it into smaller chunks wherever two adjacent characters `word[i]` and `word[i+1]` have a difference `abs(word[i] - word[i+1]) > 2`. Any complete substring must be entirely contained within one of these chunks.
2. **Process Each Chunk:** For each chunk, find the number of complete substrings and add it to a total count.
3. **Find Substrings in a Chunk:** To find complete substrings within a chunk `s`:
    a. Iterate through each possible starting index `i` of `s`.
    b. For each `i`, start a new sliding window. Use a second pointer `j` to expand the window to the right, from `i` to the end of the chunk.
    c. Maintain a frequency map for the characters in the current window `s[i...j]`.
    d. As `j` advances, update the frequency map. If any character's count exceeds `k`, this window and any further extensions from `i` are invalid, so we can break the inner loop over `j`.
    e. At each step `j`, check if the substring is complete. A key observation is that if no character count exceeds `k`, the substring is complete if and only if `(number of distinct characters) * k == (length of substring)`. If this condition is met, increment the total count.

## Linear Time Sliding Window on Chunks
The most efficient solution also starts by splitting the word into valid chunks. The key improvement is how we process each chunk. Instead of checking every possible substring, we iterate through the possible number of unique characters a complete substring can have (from 1 to 26). For each number of unique characters, `d`, we know the exact length a complete substring must have: `d * k`. We can then use a fixed-size sliding window of this length to find all such substrings in linear time for that `d`.
**Time:** O(N) - The initial split takes O(N). Processing each chunk of length `M` takes O(26 * M), which is O(M). Since the sum of all chunk lengths is `N`, the total time is O(N) + sum(O(M_i)) = O(N). · **Space:** O(1) - The space for the frequency map is constant (size 26), regardless of the input size.
**Pros:** Optimal O(N) time complexity, making it highly efficient for large inputs.; Handles all constraints of the problem effectively.
**Cons:** The implementation is more complex, requiring careful management of the sliding window and its associated counters.
### Explanation
This approach cleverly transforms the problem. By fixing the number of distinct characters `d`, we also fix the target substring length `L = d * k`. This allows us to use a very efficient fixed-size sliding window. The total work for a chunk of length `M` becomes `26 * O(M)`, which is `O(M)`. Since the sum of all chunk lengths is `N`, the total time complexity is linear.

```java
class Solution {
    public int countCompleteSubstrings(String word, int k) {
        int totalCount = 0;
        int n = word.length();
        int start = 0;
        for (int i = 1; i <= n; i++) {
            if (i == n || Math.abs(word.charAt(i) - word.charAt(i - 1)) > 2) {
                totalCount += countInChunk(word.substring(start, i), k);
                start = i;
            }
        }
        return totalCount;
    }

    private int countInChunk(String s, int k) {
        int count = 0;
        int n = s.length();
        for (int d = 1; d <= 26; d++) {
            int len = d * k;
            if (len > n) {
                break;
            }

            int[] freq = new int[26];
            int distinctCount = 0;
            int kCount = 0; // count of chars with frequency == k

            // Initialize first window
            for (int i = 0; i < len; i++) {
                int cIdx = s.charAt(i) - 'a';
                if (freq[cIdx] == 0) distinctCount++;
                freq[cIdx]++;
                if (freq[cIdx] == k) kCount++;
                if (freq[cIdx] == k + 1) kCount--;
            }

            if (distinctCount == d && kCount == d) {
                count++;
            }

            // Slide window
            for (int i = len; i < n; i++) {
                // Add char at i
                int inIdx = s.charAt(i) - 'a';
                if (freq[inIdx] == 0) distinctCount++;
                freq[inIdx]++;
                if (freq[inIdx] == k) kCount++;
                if (freq[inIdx] == k + 1) kCount--;

                // Remove char at i - len
                int outIdx = s.charAt(i - len) - 'a';
                if (freq[outIdx] == k) kCount--;
                if (freq[outIdx] == k + 1) kCount++;
                freq[outIdx]--;
                if (freq[outIdx] == 0) distinctCount--;
                
                if (distinctCount == d && kCount == d) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. **Split into Chunks:** Same as the previous approach, split `word` into chunks where `abs(char_diff) <= 2` for all adjacent characters. This takes `O(N)` time.
2. **Process Each Chunk with a Specialized Sliding Window:** For each chunk `s`:
    a. Initialize a local counter for the chunk to zero.
    b. Iterate through the possible number of distinct characters `d` a complete substring can have, from `d = 1` to `d = 26`.
    c. For each `d`, the required length of a complete substring is `L = d * k`. If `L` exceeds the chunk's length, break the loop for `d`.
    d. Use a fixed-size sliding window of length `L` to traverse the chunk.
    e. Maintain two counters for the window: `distinctCount` (number of unique characters) and `kCount` (number of characters with frequency exactly `k`).
    f. Initialize the window with the first `L` characters, calculating the initial `distinctCount` and `kCount`.
    g. Slide the window one position at a time to the right. In each step, efficiently update `distinctCount` and `kCount` in `O(1)` time by accounting for the character leaving and the character entering the window.
    h. After each slide, if `distinctCount == d` and `kCount == d`, it means the current window is a complete substring. Increment the chunk's counter.
3. **Sum Results:** The total count is the sum of counts from all chunks.

# Solutions
### Java

```java
class Solution {
public
  int countCompleteSubstrings(String word, int k) {
    int n = word.length();
    int ans = 0;
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && Math.abs(word.charAt(j) - word.charAt(j - 1)) <= 2) {
        ++j;
      }
      ans += f(word.substring(i, j), k);
      i = j;
    }
    return ans;
  }
private
  int f(String s, int k) {
    int m = s.length();
    int ans = 0;
    for (int i = 1; i <= 26 && i * k <= m; ++i) {
      int l = i * k;
      int[] cnt = new int[26];
      for (int j = 0; j < l; ++j) {
        ++cnt[s.charAt(j) - 'a'];
      }
      Map<Integer, Integer> freq = new HashMap<>();
      for (int x : cnt) {
        if (x > 0) {
          freq.merge(x, 1, Integer : : sum);
        }
      }
      if (freq.getOrDefault(k, 0) == i) {
        ++ans;
      }
      for (int j = l; j < m; ++j) {
        int a = s.charAt(j) - 'a';
        int b = s.charAt(j - l) - 'a';
        freq.merge(cnt[a], -1, Integer : : sum);
        ++cnt[a];
        freq.merge(cnt[a], 1, Integer : : sum);
        freq.merge(cnt[b], -1, Integer : : sum);
        --cnt[b];
        freq.merge(cnt[b], 1, Integer : : sum);
        if (freq.getOrDefault(k, 0) == i) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countCompleteSubstrings(string word, int k) {
    int n = word.length();
    int ans = 0;
    auto f = [&](string s) {
      int m = s.length();
      int ans = 0;
      for (int i = 1; i <= 26 && i * k <= m; ++i) {
        int l = i * k;
        int cnt[26]{};
        for (int j = 0; j < l; ++j) {
          ++cnt[s[j] - 'a'];
        }
        unordered_map<int, int> freq;
        for (int x : cnt) {
          if (x > 0) {
            freq[x]++;
          }
        }
        if (freq[k] == i) {
          ++ans;
        }
        for (int j = l; j < m; ++j) {
          int a = s[j] - 'a';
          int b = s[j - l] - 'a';
          freq[cnt[a]]--;
          cnt[a]++;
          freq[cnt[a]]++;
          freq[cnt[b]]--;
          cnt[b]--;
          freq[cnt[b]]++;
          if (freq[k] == i) {
            ++ans;
          }
        }
      }
      return ans;
    };
    for (int i = 0; i < n;) {
      int j = i + 1;
      while (j < n && abs(word[j] - word[j - 1]) <= 2) {
        ++j;
      }
      ans += f(word.substr(i, j - i));
      i = j;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countCompleteSubstrings(self, word: str, k: int) -> int: def f(s: str) -> int: m = len(s) ans = 0 for i in range(1, 27): l = i * k if l > m: break cnt = Counter(s[: l]) freq = Counter(cnt . values()) ans += freq[k] == i for j in range(l, m): freq[cnt[s[j]]] -= 1 cnt[s[j]] += 1 freq[cnt[s[j]]] += 1 freq[cnt[s[j - l]]] -= 1 cnt[s[j - l]] -= 1 freq[cnt[s[j - l]]] += 1 ans += freq[k] == i return ans n = len(word) ans = i = 0 while i < n: j = i + 1 while j < n and abs(ord(word[j]) - ord(word[j - 1])) <= 2: j += 1 ans += f(word[i: j]) i = j return ans

```