至多包含K种字符的子串

class Solution:
    def longestSubstring(self , s: str, k: int) -> int:
        char_map = defaultdict(int)
        start = 0
        end = 0
        maxlen = 0
        while end < len(s):
            char_map[s[end]] += 1
            if len(char_map) > k:
                while len(char_map) > k:
                    char_map[s[start]] -= 1
                    if char_map[s[start]] == 0:
                        del char_map[s[start]]
                    start += 1
            end += 1
            maxlen = max(maxlen, end - start)
        return maxlen

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param k int整型 
# @return int整型
#
# 问题一：如何判断子串包含多少种不同字符
# hash，hash对应value不为0的key的个数
# k为限定条件，即不能使对应的value不为9的key的个数超过k，若超过，则移动左界
class Solution:
    def longestSubstring(self , s: str, k: int) -> int:
        # write code here
        if len(s) <= 1:
            return len(s)
        # 定义空字典
        dict_ = {}
        # 初始化左右界
        left = right = 0
        res = 0
        key_count = 0
        # 进入循环
        while right < len(s):
            # 将当前right的字符加入或者更新其在dict_中的value
            # 需要判断当前字符是否在字典之中
            if s[right] not in dict_:
                # 初始化key
                key_count += 1
                dict_[s[right]] = 1
            else:
                if dict_[s[right]] == 0:
                    key_count += 1
                # 更新对应key的value
                dict_[s[right]] += 1
            # 如果value >= 1的key的个数超过了k，则需要移动左界并更新字典，直到满足条件
            if key_count > k:
                while True:
                    # 把左界上面的字符的value清为0，就维持了条件
                    # 具体操作：更新value，移动左界
                    dict_[s[left]] -= 1
                    # 如果-1之后，左界指向的字符在字典里面value等于0了，移动左界并且跳出循环
                    if dict_[s[left]] == 0:
                        left += 1
                        break
                    # 不满足上面的条件，移动左界，进行循环
                    left += 1
                # 清零之后，更新一下key_count
                key_count -= 1
            # 经过上面的判断，此时必然满足条件，则计算子串长度，并与上一个res比较，如果更大，则更新res
            temp_res = right - left + 1
            if temp_res > res:
                res = temp_res
            # 在最后，移动右界
            right += 1

        return res

# python3
class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # write code here
        lastPos = {}
        l, res = 0, 0
        for r in range(len(s)):
            if s[r] in lastPos:
                lastPos[s[r]] = r
            else:
                if len(lastPos) < k:
                    lastPos[s[r]] = r
                else:
                    lastPos[s[r]] = r
                    while l < lastPos[s[l]]:
                        l += 1
                    lastPos.pop(s[l], None)
                    l += 1
            res = max(res, r - l + 1)
        return res