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

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.执行结果