To solve this problem, we need to find the number of substrings of a given string ( S ) that contain exactly ( k ) distinct characters. The key insight here is to use the sliding window technique to count substrings with at most ( k ) distinct characters and subtract the count of substrings with at most ( k-1 ) distinct characters. This approach efficiently computes the desired result in linear time.

Approach

1. Helper Function: The helper function calculates the number of substrings with at most ( k ) distinct characters using a sliding window (two pointers) technique:

   • Sliding Window: Maintain a window [left, right] where the number of distinct characters does not exceed ( k ).
   • Frequency Array: Use an array of size 26 (for lowercase letters) to count the frequency of each character in the current window.
   • Adjust Window: If the number of distinct characters exceeds ( k ), move the left pointer to the right until the window is valid again.
   • Count Substrings: For each valid window ending at the right pointer, the number of valid substrings is ( right - left + 1 ).

2. Main Calculation: The number of substrings with exactly ( k ) distinct characters is the difference between the count of substrings with at most ( k ) distinct characters and the count of substrings with at most ( k-1 ) distinct characters.

Solution Code

def count_k_distinct_substrings(s, k):
    def helper(s, k):
        if k < 0:
            return 0
        freq = [0] * 26
        left = 0
        distinct = 0
        count = 0
        for right in range(len(s)):
            c = s[right]
            idx = ord(c) - ord('a')
            if freq[idx] == 0:
                distinct += 1
            freq[idx] += 1

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

            count += right - left + 1
        return count

    return helper(s, k) - helper(s, k-1)

Explanation

• Helper Function: This function efficiently counts the number of substrings with at most ( k ) distinct characters. It uses a sliding window to maintain valid substrings and updates the count as the right pointer moves.
• Main Function: By subtracting the count of substrings with at most ( k-1 ) distinct characters from the count of substrings with at most ( k ) distinct characters, we get the number of substrings with exactly ( k ) distinct characters.

This approach runs in ( O(n) ) time complexity (where ( n ) is the length of the string) because each character is processed at most twice (once by the right pointer and once by the left pointer). The space complexity is ( O(1) ) since we use a fixed-size array of 26 elements.

Example: For ( S = "abc" ) and ( k = 2 ):

• Helper(2) = 5 (substrings: "a", "ab", "b", "bc", "c")
• Helper(1) = 3 (substrings: "a", "b", "c")
• Result: ( 5 - 3 = 2 ) (substrings: "ab", "bc")

This solution is optimal and handles all edge cases, including ( k = 0 ) (returns 0) and ( k ) larger than the number of distinct characters in the string (returns 0). It is efficient and works well for large input sizes.

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