*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)