To solve this problem, we need to find the length of the longest substring of a given string s that contains exactly k distinct characters. If no such substring exists, we return 0.

Approach

The optimal approach to solve this problem efficiently is using the sliding window technique combined with a frequency dictionary to track the count of characters in the current window. Here's a detailed breakdown of the approach:

1. Sliding Window: We use two pointers (left and right) to represent the current window of characters in the string. The right pointer expands the window by moving to the right, while the left pointer contracts the window when the number of distinct characters exceeds k.
2. Frequency Dictionary: This dictionary keeps track of the count of each character in the current window. It helps us quickly determine the number of distinct characters in the window.
3. Adjust Window: When the number of distinct characters in the window exceeds k, we move the left pointer to the right until the number of distinct characters is within the limit.
4. Track Maximum Length: Whenever the number of distinct characters in the window is exactly k, we calculate the length of the window and update the maximum length if the current window is longer.

Solution Code

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0

    left = 0
    max_len = 0
    freq = {}

    for right in range(len(s)):
        char = s[right]
        freq[char] = freq.get(char, 0) + 1

        # Shrink the window from the left if distinct count exceeds k
        while len(freq) > k:
            left_char = s[left]
            freq[left_char] -= 1
            if freq[left_char] == 0:
                del freq[left_char]
            left += 1

        # Update max length if current window has exactly k distinct characters
        if len(freq) == k:
            current_len = right - left + 1
            if current_len > max_len:
                max_len = current_len

    return max_len

Explanation

• Edge Cases: If k is 0 or the string s is empty, we immediately return 0 since no valid substring exists.
• Expanding the Window: The right pointer moves to the right, adding each character to the frequency dictionary.
• Contracting the Window: When the number of distinct characters in the window exceeds k, we move the left pointer to the right, decrementing the count of the character at the left pointer. If the count becomes zero, we remove the character from the frequency dictionary to maintain accurate distinct count.
• Max Length Calculation: Whenever the number of distinct characters in the window is exactly k, we compute the length of the window and update the maximum length if necessary.

This approach ensures that each character is processed at most twice (once by the right pointer and once by the left pointer), leading to an O(n) time complexity where n is the length of the string. The space complexity is O(k) since the frequency dictionary can hold at most k distinct characters at any time.

This solution efficiently handles all test cases and provides the correct result for the problem.

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