LeetCode Solutions Blog

Count Complete Substrings

Number: 3223

Difficulty: Hard

Paid? No

Companies: Meesho

Problem Description

Given a string word and an integer k, count the number of complete substrings in word. A substring s is complete if: • Each distinct character in s appears exactly k times. • The absolute difference between two adjacent characters’ positions in the alphabet is at most 2. A substring is a contiguous non-empty part of the string.

Key Insights

A complete substring must have length d * k, where d is the number of distinct characters in the substring.
For each possible d (from 1 to at most 26), the window length is L = d * k.
Use a sliding window of fixed length L and maintain a frequency table for 26 letters.
To check the “adjacent difference” condition efficiently, precompute an array (and its prefix sum) where each entry indicates whether a pair of adjacent characters is valid (i.e. their difference is at most 2). This allows O(1) verification per window.
Maintain counters for distinct letters and letters with frequency exactly k while sliding the window to avoid recounting frequencies from scratch.

Space and Time Complexity

Time Complexity: O(26 * n) ≈ O(n) where n is the length of word, since we cycle through at most 26 window types and use a constant-time update per window. Space Complexity: O(n + 26) ≈ O(n) due to the prefix sum array for adjacent validity and the frequency count array.

Solution

The solution iterates over possible distinct letter counts d (from 1 to 26) and fixes the window length L = d * k. For each such window sliding over word:

Use a frequency table to count characters in the window.
Maintain two counters: one for the number of distinct characters and one for how many characters appear exactly k times.
Check the frequency condition: the number of distinct characters must be d and each of these characters appears exactly k times.
Use a precomputed prefix sum array for adjacent validity to verify that in the current window the difference between every adjacent character is at most 2.
Update the frequency table and counters as the window slides.
Sum up the count of valid windows. This approach leverages sliding windows with careful bookkeeping and O(1) validity checks per window, ensuring efficiency even for large inputs.

Code Solutions

# Python code solution with line-by-line comments
def countCompleteSubstrings(word: str, k: int) -> int:
    n = len(word)
    # Precompute validity array for adjacent characters.
    # valid[i] = 1 if abs(ord(word[i+1]) - ord(word[i])) <= 2, for i in range(n - 1); else 0.
    valid = [1 if abs(ord(word[i+1]) - ord(word[i])) <= 2 else 0 for i in range(n - 1)]
    # Build prefix sum array for valid differences.
    prefix = [0] * (n)
    for i in range(1, n):
        prefix[i] = prefix[i-1] + valid[i-1]
    
    result = 0
    # Iterate for possible number of distinct letters d
    for d in range(1, 27):
        L = d * k  # window length must be exactly d * k
        if L > n:
            break
        # Frequency array for 26 letters.
        freq = [0] * 26
        distinct = 0         # count of distinct letters in the window.
        countExact = 0       # count of letters that appear exactly k times.
        
        # Initialize the first window.
        for i in range(L):
            idx = ord(word[i]) - ord('a')
            if freq[idx] == 0:
                distinct += 1
            freq[idx] += 1
            if freq[idx] == k:
                countExact += 1
            # If frequency goes above k, we ignore for now; condition will fail.
            if freq[idx] == k + 1:
                countExact -= 1
        
        # Function to check if all adjacent differences in window [start, start+L-1] are valid.
        def is_adjacent_valid(start):
            # In window of length L, there are L-1 adjacent pairs.
            return (prefix[start + L - 1] - prefix[start]) == (L - 1)
        
        # Slide over all windows of length L.
        if distinct == d and countExact == d and is_adjacent_valid(0):
            result += 1
        
        for start in range(1, n - L + 1):
            # Remove the leftmost character.
            left_idx = ord(word[start - 1]) - ord('a')
            if freq[left_idx] == k:
                countExact -= 1
            freq[left_idx] -= 1
            if freq[left_idx] == 0:
                distinct -= 1
            if freq[left_idx] == k:
                countExact += 1
                
            # Add the new rightmost character.
            right_idx = ord(word[start + L - 1]) - ord('a')
            if freq[right_idx] == 0:
                distinct += 1
            if freq[right_idx] == k:
                countExact -= 1
            freq[right_idx] += 1
            if freq[right_idx] == k:
                countExact += 1
            if freq[right_idx] == k + 1:
                countExact -= 1
            
            # Check both frequency and adjacent condition.
            if distinct == d and countExact == d and is_adjacent_valid(start):
                result += 1

    return result

# Example usage:
print(countCompleteSubstrings("igigee", 2))  # Expected output: 3
print(countCompleteSubstrings("aaabbbccc", 3))  # Expected output: 6