340. Longest Substring with At Most K Distinct Characters

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

跟159题一样，只是把临界值2换成k

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        res = 0
        freq = dict()
        count = 0
        
        l, r = 0, 0
        while r < len(s):
            # 把右指针字符加进统计
            freq[s[r]] = freq.get(s[r], 0) + 1
            
            # 如果s[r]是new distinct character，就计数
            if freq[s[r]] == 1: count += 1
            # 当计数超过2时，触发左指针移动，直到计数不再大于2
            while count > k:
                # 左指针字符的统计要-1
                freq[s[l]] -= 1
                # 如果移出的左指针字符已经是该字符最后一个，计数-1
                if freq[s[l]] == 0: count -= 1
                l += 1
            
            # 如果当前window更长，就更新结果
            res = max(res, r+1-l)
            
            r += 1
        
            
        return len(s) if len(s)<=k else res