Efficient Substring Counting Using Segmentation and Sliding Window
# IntuitionThe problem involves counting "complete substrings," defined as substrings where the number of unique characters matches the specified frequency k. B
### # Intuition
The problem involves counting "complete substrings," defined as substrings where the number of unique characters matches the specified frequency `k`. By leveraging the sliding window technique and segmenting the string based on specific character differences, we efficiently reduce the search space while accurately counting substrings.

The intuition is rooted in two ideas:
1. **Sliding Window**: Efficiently track character counts and dynamically adjust the window size based on constraints.
2. **Segmentation**: Break the string into meaningful parts to avoid unnecessary computations on substrings that cannot satisfy the conditions.

### # Approach
1. **Segment Division**:
   - Split the input string into segments where adjacent characters differ by more than 2 in ASCII value (`abs(ord(word[i]) - ord(word[i - 1])) > 2`).
   - This ensures each segment is self-contained, simplifying substring validation.

2. **Sliding Window within Segments**:
   - Use a sliding window to traverse each segment and calculate the frequency of characters in substrings of increasing sizes (`window_size = unique_char * k`).
   - Maintain a dictionary (`default_dict`) to track character frequencies within the current window.

3. **Validation and Result Calculation**:
   - Validate substrings by checking if the number of valid characters in the current window matches the expected count (`unique_char`).
   - Increment the result (`result`) for each valid substring.

4. **Final Processing**:
   - Handle the last segment separately to ensure all characters are included.

### # Complexity
- **Time Complexity**:
  - In the `solve` function, the outer loop iterates over up to 26 unique character counts, and the sliding window processes the segment. This results in a total complexity of $$O(n^2)$$.

- **Space Complexity**:
  - The dictionary used for character frequency (`default_dict`) stores up to 26 keys (one for each letter of the alphabet). Hence, the space complexity is $$O(1)$$.

### # Code
```python3 []
class Solution:
    def countCompleteSubstrings(self, word: str, k: int) -> int:
        # Initialize result and word length
        n = len(word)
        result = 0

        # Helper function to process a substring
        def solve(start, end):
            nonlocal result
            for unique_char in range(1, 27):
                if unique_char * k > end - start + 1:
                    break
                left = start
                right = start
                default_dict = defaultdict(int)
                possible_res = 0
                while right <= end:
                    ch = word[right]
                    default_dict[ch] += 1
                    if default_dict[ch] == k:
                        possible_res += 1
                    elif default_dict[ch] == k + 1:
                        possible_res -= 1
                    if right - left + 1 > unique_char * k:
                        default_dict[word[left]] -= 1
                        if default_dict[word[left]] == k:
                            possible_res += 1
                        elif default_dict[word[left]] == k - 1:
                            possible_res -= 1
                        left += 1
                    
                    if possible_res == unique_char:
                        result += 1
                    right += 1

        # Iterate through segments of the word
        segment_start = 0

        for segment_end in range(1, n):
            if abs(ord(word[segment_end]) - ord(word[segment_end - 1])) > 2:
                solve(segment_start, segment_end - 1)
                segment_start = segment_end

        # Final segment
        solve(segment_start, n - 1)

        return result
```
😊
['Python3']