To solve this problem, we need to find the number of substrings in a given string that have exactly k distinct characters. The optimal approach involves using the sliding window technique to efficiently compute the result by leveraging the difference between the number of substrings with at most k distinct characters and those with at most k-1 distinct characters.

Approach

1. Key Insight: The number of substrings with exactly k distinct characters can be derived by subtracting the number of substrings with at most k-1 distinct characters from the number of substrings with at most k distinct characters. This is because:

   • Let f(k) = number of substrings with at most k distinct characters.
   • The result for exactly k distinct characters is f(k) - f(k-1).

2. Sliding Window Technique: For computing f(k), we use a sliding window (two pointers) approach:

   • Maintain a frequency array to count occurrences of each character in the current window.
   • Expand the window by moving the right pointer and update the frequency of the current character.
   • If the number of distinct characters exceeds k, shrink the window from the left until the number of distinct characters is within the limit.
   • For each valid window ending at the right pointer, the number of valid substrings is right - left + 1 (all substrings from left to right ending at right).

Solution Code

def count_k_distinct(s: str, k: int) -> int:
    def at_most(k_val: int) -> int:
        if k_val <= 0:
            return 0
        freq = [0] * 26
        left = 0
        distinct = 0
        result = 0
        for right in range(len(s)):
            char_idx = ord(s[right]) - ord('a')
            if freq[char_idx] == 0:
                distinct += 1
            freq[char_idx] += 1

            while distinct > k_val:
                left_char_idx = ord(s[left]) - ord('a')
                freq[left_char_idx] -= 1
                if freq[left_char_idx] == 0:
                    distinct -= 1
                left += 1

            result += right - left + 1
        return result

    return at_most(k) - at_most(k-1)

Explanation

• Helper Function at_most(k_val): This function calculates the number of substrings with at most k_val distinct characters. It uses a sliding window to efficiently count these substrings.
• Main Calculation: The main function subtracts the result of at_most(k-1) from at_most(k) to get the number of substrings with exactly k distinct characters.

This approach ensures an efficient time complexity of O(n) (since each character is processed twice, once by the right pointer and once by the left pointer) and a space complexity of O(1) (fixed-size frequency array for 26 lowercase letters). This makes it suitable for large input strings.

Example: For s = "abc" and k = 2, the result is 2 (substrings "ab" and "bc"). The function at_most(2) returns 5 (substrings: "a", "ab", "b", "bc", "c") and at_most(1) returns 3 (substrings: "a", "b", "c"), so 5-3=2.

This solution handles all edge cases, including k=0 (returns 0), k larger than the number of distinct characters in the string (returns 0), and strings with all characters the same (returns the total number of substrings if k=1).

Overall, this is an optimal and efficient solution for the problem.

作者声明:本文包含人工智能生成内容。