Solution Explanation: Number of Equal Count Substrings

This problem asks us to find the number of substrings where each unique character appears exactly count times. The solution uses a sliding window approach enhanced with a frequency counter to efficiently track character counts within the window.

Approach

The core idea is to iterate through possible substring lengths. Since each unique character must appear count times, the length of any qualifying substring must be a multiple of count. We iterate through possible numbers of unique characters (from 1 to 26). For each number i, the substring length will be i * count.

A sliding window of this length moves across the string. Inside the window, we maintain a frequency count of each character using a Counter (Python) or an array (other languages). We check if the number of characters with frequency count matches i. If they do, we've found an equal count substring.

Time Complexity Analysis

• Outer loop: Iterates from i = 1 to 26 (or until i * count exceeds string length). This is O(26) which simplifies to O(1).
• Inner loop: Iterates through the string once for each i. The sliding window's movement is amortized O(n), where n is the string length.
• Overall: The dominant factor is the nested loop resulting in O(n). Although there's a nested loop, the outer loop's iteration count is a constant (26). Thus the overall time complexity is O(n).

Space Complexity Analysis

The space complexity is dominated by the frequency counter. In the worst case, the counter holds counts for all 26 lowercase letters. Therefore, the space complexity is O(1) (constant).

Code Implementation (Python)

from collections import Counter
 
class Solution:
    def equalCountSubstrings(self, s: str, count: int) -> int:
        ans = 0
        n = len(s)
        for i in range(1, 27): # Iterate through possible numbers of unique characters
            k = i * count      # Length of substring for i unique characters
            if k > n:          # Optimization: Skip if substring length exceeds string length
                break
            cnt = Counter()    # Frequency counter for characters
            t = 0              # Count of characters with frequency = count
            for j, c in enumerate(s):
                cnt[c] += 1
                if cnt[c] == count:  # Increment t if character frequency reaches count
                    t += 1
                elif cnt[c] == count + 1:  # Decrement t if character frequency exceeds count
                    t -= 1
                if j >= k:  # Sliding window: remove character from the left side if needed
                    cnt[s[j - k]] -= 1
                    if cnt[s[j - k]] == count:  # Adjust t for removed character
                        t += 1
                    elif cnt[s[j - k]] == count -1:
                        t -= 1
                if i == t:  # Check if the number of characters with freq=count equals i
                    ans += 1
        return ans
 

The other language implementations (Java, C++, Go, TypeScript, JavaScript) follow a very similar structure, using arrays instead of Counter for frequency counting. The core logic remains the same: the sliding window and the character frequency counting.