We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Equal Count Substrings

Number: 2209

Difficulty: Medium

Paid? Yes

Companies: Cisco

Problem Description

Given a 0-indexed string s consisting only of lowercase English letters and an integer count, return the number of substrings in s where each unique letter appears exactly count times. A substring is a contiguous non-empty sequence of characters in s.

Key Insights

  • A valid substring must have its length equal to (uniqueLetterCount * count).
  • For any valid substring, every character present must appear exactly count times.
  • Instead of checking all substrings, iterate over possible numbers of unique letters (from 1 to 26) and fix a window length = uniqueCount * count.
  • Use a sliding window to update character frequencies in constant time.
  • Count the number of windows where: (1) the number of unique characters equals the expected uniqueCount, and (2) every character in the window appears exactly count times.

Space and Time Complexity

Time Complexity: O(26 * n) ≈ O(n), since we try each possible unique letter count (at most 26) and slide over s. Space Complexity: O(26) = O(1) for the frequency array and auxiliary counters.

Solution

For each unique letter count from 1 to 26, compute window_length = uniqueCount * count. If window_length exceeds s.length, break out of the loop. For each fixed-size window, use a frequency array of size 26 and maintain two counters: one for the number of unique letters currently in the window, and one for the number of letters that appear exactly count times. First, initialize the frequency array for the first window. Then slide the window one character at a time updating the frequency of the character that goes out and coming in. For each window, if both the number of unique letters and the count of letters with exactly count occurrences are equal to the chosen uniqueCount, it qualifies as a valid substring and you update the answer.

Code Solutions

def equal_count_substrings(s: str, count: int) -> int:
    result = 0
    n = len(s)
    
    # Try all possible unique letter counts from 1 to 26.
    for unique_count in range(1, 27):
        window_length = unique_count * count
        if window_length > n:
            break
        
        # Initialize frequency array and counters for the first window.
        freq = [0] * 26
        current_unique = 0  # Number of characters with non-zero frequency.
        count_exact = 0     # Number of characters occurring exactly 'count' times.
        
        for i in range(window_length):
            idx = ord(s[i]) - ord('a')
            freq[idx] += 1
            if freq[idx] == 1:
                current_unique += 1
            if freq[idx] == count:
                count_exact += 1
            if freq[idx] == count + 1:
                count_exact -= 1
        
        if current_unique == unique_count and count_exact == unique_count:
            result += 1
        
        # Slide the window across the string.
        for i in range(window_length, n):
            # Remove the character at the left of the window.
            left_idx = ord(s[i - window_length]) - ord('a')
            if freq[left_idx] == count:
                count_exact -= 1
            freq[left_idx] -= 1
            if freq[left_idx] == 0:
                current_unique -= 1
            
            # Add the new character at the right.
            right_idx = ord(s[i]) - ord('a')
            if freq[right_idx] == 0:
                current_unique += 1
            if freq[right_idx] == count:
                count_exact -= 1
            freq[right_idx] += 1
            if freq[right_idx] == count:
                count_exact += 1
            
            if current_unique == unique_count and count_exact == unique_count:
                result += 1
                
    return result

# Example usage:
print(equal_count_substrings("aaabcbbcc", 3))  # Expected Output: 3
← Back to All Questions