340.至多包含 K 个不同字符的最长子串(Hard)

题目描述

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

样例

Input: s = "eceba", k = 2
Output: 3
# 最长的子串是 eca
Input: s = "aa", k = 1
Output: 2
# 最长的子串是 aa

题解

本题算是 无重复子串的最长子串 的改编，解题思路也很相近。就是需要单独记录一下不重复元素的个数，

代码

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        l, r = 0, -1 
        n = len(s)
        visited = collections.defaultdict(int)
        diffs = 0  # 专门用于记录不重复元素个数
        ans = 0
        while r + 1 < n:
            r += 1
            if visited[s[r]] == 0:
                diffs += 1
            visited[s[r]] += 1
            if diffs > k:
                visited[s[l]] -= 1
                if visited[s[l]] == 0:
                    diffs -= 1
                l += 1 # 左指针右移
            elif diffs <= k:
                ans = max(ans, r - l + 1)
        return ans