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, which allows us to efficiently track the longest valid substring using two pointers.
Approach
The sliding window technique involves maintaining a window defined by two pointers (left and right) that represent the current substring we are examining. Here's the step-by-step approach:
- Frequency Map: Use a frequency map to keep track of the count of each character within the current window.
- Expand the Window: Move the
rightpointer to include new characters in the window, updating the frequency map. - Shrink the Window: If the number of distinct characters in the window exceeds
k, move theleftpointer to the right until the number of distinct characters is within the limit. - Update Maximum Length: At each step, calculate the length of the current valid window and update the maximum length if the current window is longer.
Solution Code
from collections import defaultdict
def longest_substring_with_k_distinct(s: str, k: int) -> int:
freq = defaultdict(int)
left = 0
max_len = 0
for right in range(len(s)):
char = s[right]
freq[char] += 1
# Shrink the window if the number of distinct characters 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 the maximum length of the valid window
current_len = right - left + 1
if current_len > max_len:
max_len = current_len
return max_len
Explanation
- Frequency Map: The
defaultdictfrom thecollectionsmodule is used to count occurrences of each character in the current window. This helps in quickly checking the number of distinct characters. - Sliding Window: The
rightpointer expands the window by adding new characters. When the number of distinct characters exceedsk, theleftpointer is moved to the right, reducing the window size until the number of distinct characters is within the limit. - Efficiency: Each character is processed exactly twice (once by the
rightpointer and once by theleftpointer), leading to an O(n) time complexity, wherenis the length of the string. The space complexity is O(k) since the frequency map can hold at mostkdistinct characters at any time.
This approach efficiently finds the longest substring with at most k distinct characters, making it suitable for large input sizes.


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