Number of Equal Count Substrings

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def equalCountSubstrings(self, s: str, count: int) -> int:
        result = 0

        for unique in range(1, 27): # Iterate through 1 to 26 unique characters
            left = 0
            right = 0
            char_count = [0] * 26 # Array to store the count of characters in the window
            has_count = 0 # Number of unique characters that appear count times

            # Iterate through the string with a sliding window
            while right < len(s):
                # Add character at right to the window
                char_count[ord(s[right]) - ord('a')] += 1

                # Check if character at right appears count times
                if char_count[ord(s[right]) - ord('a')] == count:
                    has_count += 1

                # Move the left side of the window if window size exceeds count * unique
                if right - left + 1 > count * unique:
                    if char_count[ord(s[left]) - ord('a')] == count:
                        has_count -= 1
                    char_count[ord(s[left]) - ord('a')] -= 1
                    left += 1

                # Check if unique characters have the right count
                if right - left + 1 == count * unique and has_count == unique:
                    result += 1

                right += 1

        return result

  1. Understanding the Problem: The task is to find substrings where each unique letter appears exactly count times. It might seem difficult at first, but the approach is quite logical.

  2. Fixed Number of Unique Characters: We can start by fixing the number of unique characters that a substring must contain. For example, we might say that the substring must contain exactly 5 unique characters.

  3. Sliding Window Approach: This is a common method used in algorithms to analyze a contiguous sequence of elements. Imagine a window of a fixed size that “slides” across the string. The window’s size is determined by multiplying the number of unique characters (unique) by the required count of each character (count).

  4. Looping Through Unique Characters: Since English letters have 26 characters, we will need to run the sliding window algorithm up to 26 times, one for each possible number of exact unique characters.

  5. For Each Unique, Run the Algorithm:

    • unique tracks the exact number of unique characters we want (e.g., 1, 2, …, 26).
    • has_count is the number of unique characters that appear exactly count times within the window.
    • We move the right side of the window to maintain the same size and adjust has_count.
    • If the number of unique characters with the correct count equals unique, we have found a valid substring, and we increment the count.

  6. Why This Works: Because the window size is fixed, if one of the characters appears more than count times, another character will have to appear less. Therefore, having a fixed number of unique characters ensures that we don’t have more or fewer characters than the exact count.

  7. Insight: The insight to fix the number of unique characters in a substring and then apply the sliding window approach is key to this solution. It simplifies the problem and helps in implementing an efficient algorithm.

  8. Credit: The explanation acknowledges summerzhou for this observation, showing respect for the contributions of others in understanding or solving the problem.

This approach leverages the sliding window technique by focusing on the exact number of unique characters within each window. It provides a systematic way to explore all possibilities and identify the substrings where each unique letter appears exactly count times.