*340. Longest Substring with At Most K Distinct Characters
https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
solution
至多包含 K 个不同字符的最长子串
from collections import Counter
class Solution:
def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
char_count = Counter()
max_length = start_index = 0
for i, char in enumerate(s):
char_count[char] += 1
while len(char_count) > k:
char_count[s[start_index]] -= 1
if char_count[s[start_index]] == 0:
del char_count[s[start_index]]
start_index += 1
max_length = max(max_length, i - start_index + 1)
return max_length
时间复杂度:O(n) 空间复杂度:O(k)
Last updated