To solve this problem, we need to find the length of the longest substring in a given string that contains at most k distinct characters. This is a classic sliding window problem where we maintain a window of characters and adjust its size to meet the condition of having at most k distinct characters.

Approach

1. Sliding Window Technique: We use two pointers (left and right) to represent the current window of characters.
2. Hash Map: A hash map (dictionary) is used to keep track of the count of each character within the current window.
3. Adjust Window: As we expand the window using the right pointer, we check if the number of distinct characters exceeds k. If it does, we shrink the window from the left until the number of distinct characters is within the limit.
4. Max Length: We keep updating the maximum length of the valid window as we iterate through the string.

Solution Code

from collections import defaultdict

def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    char_count = defaultdict(int)
    left = 0
    max_len = 0

    for right in range(len(s)):
        char = s[right]
        char_count[char] += 1

        # Shrink the window if the number of distinct characters exceeds k
        while len(char_count) > k:
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                del char_count[left_char]
            left += 1

        # Update the maximum length of the valid window
        max_len = max(max_len, right - left + 1)

    return max_len

Explanation

1. Initialization: We start with left pointer at 0, max_len set to 0, and a char_count dict to track character counts.
2. Expand Window: For each character at the right pointer, we increment its count in the dict.
3. Shrink Window: If the number of distinct characters in char_count 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 dict.
4. Update Max Length: After adjusting the window, we check if the current window length (from left to right) is the longest valid window so far and update max_len accordingly.

Complexity

• Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once by the right pointer and once by the left pointer).
• Space Complexity: O(k), since the dict can hold at most k+1 characters (we shrink the window when it exceeds k).

This approach efficiently finds the longest substring with at most k distinct characters using the sliding window technique, ensuring optimal performance.

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