0340. 至多包含 K 个不同字符的最长子串 #
- 标签:哈希表、字符串、滑动窗口
- 难度:中等
题目大意 #
给定一个字符串 s
,
要求:返回至多包含 k
个不同字符的最长子串 t
的长度。
解题思路 #
用滑动窗口 window_counts
来记录各个字符个数,window_counts
为哈希表类型。用 ans
来维护至多包含 k
个不同字符的最长子串 t
的长度。
设定两个指针:left
、right
,分别指向滑动窗口的左右边界,保证窗口中不超过 k
种字符。
- 一开始,
left
、right
都指向0
。 - 将最右侧字符
s[right]
加入当前窗口window_counts
中,记录该字符个数,向右移动right
。 - 如果该窗口中字符的种数多于
k
个,即len(window_counts) > k
,则不断右移left
,缩小滑动窗口长度,并更新窗口中对应字符的个数,直到len(window_counts) <= k
。 - 维护更新至多包含
k
个不同字符的最长子串t
的长度。然后继续右移right
,直到right >= len(nums)
结束。 - 输出答案
ans
。
代码 #
|
|