1.题目基本信息
1.1.题目描述
给你一个字符串 s 和一个整数 k ，请你找出 至多 包含 k 个 不同 字符的最长子串，并返回该子串的长度。
1.2.题目地址
https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/description/
2.解题方法
2.1.解题思路
滑动窗口
2.2.解题步骤
第一步，构建维护变量。left,right俩指针维护一个滑动窗口；map_维护滑动窗口中每个字符的最右侧的字符串的索引；currentLength维护当前的不同字符子串的长度
第二步，滑动窗口进行滑动，更新currentLength和maxLength
3.解题代码
python代码
class Solution:# 重点: 双指针+map记录滑动窗口内各字符的最右侧索引# 注意: 区分maxLength和currentLengthdef lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:if k==0:return 0length=len(s)# 第一步，构建维护变量。left,right俩指针维护一个滑动窗口；map_维护滑动窗口中每个字符的最右侧的字符串的索引；currentLength维护当前的不同字符子串的长度left,right=0,0map_={}currentLength=0# 第二步，滑动窗口进行滑动，更新currentLength和maxLengthmaxLength=1for i in range(length):map_[s[i]]=iright=iif len(map_)>k: # 删除最小索引的字符minIndex=min(map_.values())for item in map_.copy().items():if item[1]==minIndex:# 更新滑动窗口左侧指针left=map_[item[0]]+1del map_[item[0]]breakcurrentLength=right-left+1else:currentLength+=1maxLength=max(maxLength,currentLength)return maxLength
4.执行结果
