题解 | #至多包含K种字符的子串#

解题思路：

1、使用前后两个指针，移动后指针遍历字符串，把每个字符出现的位置创建为列表，并存入字典；使用res记录结果，初始值为0；

2、后指针对应字符在字典中，或字典中的字符种类没有超过k种，则直接把索引存入字典；

3、如果对应字符不在字典中，且字典中字符种类等于k种，则记录当前子串大小并更新res；

寻找可以减少子串中一种字符且前指针移动最短的位置，即找到字典中各字符对应列表的最大值最小的一个字符，把前指针移动到该字符最后一次出现的下一个位置，并删除字典中该字符对应的键值对；

4、后指针移动到最后一个位置后，再更新一次res。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param k int整型 
# @return int整型
#
class Solution:
    
    def getRes(self,start,end,res):
        if end - start > res:
            res = end - start
        return res
    def getSmallerItem(self,nums):
        keys_list = list(nums.keys())
        print(keys_list)
        res = keys_list[0]
        for i in keys_list:
            if max(nums[i]) < max(nums[res]):
                res = i
        return res

    def longestSubstring(self , s: str, k: int) -> int:
        start = 0
        end = 0
        length = len(s)
        nums = {}
        res = 0
        while end < length:
            if s[end] in nums:
                nums[s[end]].append(end)
                end += 1
            else:
                if len(nums) < k:
                    index_list = [end]
                    nums[s[end]] = index_list
                    end += 1
                else:
                    res = self.getRes(start,end,res)
                    smaller_item = self.getSmallerItem(nums)
                    start = nums[smaller_item][-1] + 1
                    nums.pop(smaller_item)
            if end == length:
                res = self.getRes(start,end,res)
        return res