LeetCode 340题：如何找到至多包含K个不同字符的最长子串？
- 内容介绍
- 文章标签
- 相关推荐
本文共计599个文字，预计阅读时间需要3分钟。
题目：给定一个字符串s和一个整数k，找出包含至多k个不同字符的最长子串的长度。
输入：字符串s=eceba，k=2
输出：3
解释：最长的包含至多2个不同字符的子串是ece，长度为3。
340.至多包含 K 个不同字符的最长子串题目描述知识点：字符串；滑动窗口
给定一个字符串 s ，找出 至多 包含k个不同字符的最长子串 t 。
示例示例 1：
输入: s = "eceba", k = 2
输出: 3
解释: 则 T 为 "ece"，所以长度为 3。
示例 2:
输入: s = "aa", k = 1
输出: 2
解释: 则 T 为 "aa"，所以长度为 2。
。
解法一：滑动窗口
这其实也是滑动窗口的一道典型题目
刚看题目，最长子串，其实应该自然的想到滑动窗口。 最大，往往都是right向右移动寻找最优解，然后破坏了条件，然后left移动，缩小窗口，继续形成可行解；
对应到这道题目：
1.right右移，试图寻找一个最长窗口，直至破坏了条件，也就是包含了大于k个字符
步骤一我们需要在窗口内含有第三个字符的时候停下来，自然想到了哈希表，当哈希表长度为3的时候，证明第k+1个字符出现了
这时候就需要去移动左窗口了
2.left开始移动，缩小窗口
left移动到哪个位置呢？我们的目的是让left移动后窗口重新满足条件，也就是只有k个字符，
所以需要把一个字符移出去，也就是移到索引最小的位置+1处
例如例1，需要移动到c后面，而不能移动到第2个e后面，所以哈希表的value值应该是字符c最后一次出现的索引，
而我们要的就是找到这两个字符谁的索引小，所以可以直接对其value形成的list进行排序，取第一个即可。
本文共计599个文字，预计阅读时间需要3分钟。
题目：给定一个字符串s和一个整数k，找出包含至多k个不同字符的最长子串的长度。
输入：字符串s=eceba，k=2
输出：3
解释：最长的包含至多2个不同字符的子串是ece，长度为3。
340.至多包含 K 个不同字符的最长子串题目描述知识点：字符串；滑动窗口
给定一个字符串 s ，找出 至多 包含k个不同字符的最长子串 t 。
示例示例 1：
输入: s = "eceba", k = 2
输出: 3
解释: 则 T 为 "ece"，所以长度为 3。
示例 2:
输入: s = "aa", k = 1
输出: 2
解释: 则 T 为 "aa"，所以长度为 2。
。
解法一：滑动窗口
这其实也是滑动窗口的一道典型题目
刚看题目，最长子串，其实应该自然的想到滑动窗口。 最大，往往都是right向右移动寻找最优解，然后破坏了条件，然后left移动，缩小窗口，继续形成可行解；
对应到这道题目：
1.right右移，试图寻找一个最长窗口，直至破坏了条件，也就是包含了大于k个字符
步骤一我们需要在窗口内含有第三个字符的时候停下来，自然想到了哈希表，当哈希表长度为3的时候，证明第k+1个字符出现了
这时候就需要去移动左窗口了
2.left开始移动，缩小窗口
left移动到哪个位置呢？我们的目的是让left移动后窗口重新满足条件，也就是只有k个字符，
所以需要把一个字符移出去，也就是移到索引最小的位置+1处
例如例1，需要移动到c后面，而不能移动到第2个e后面，所以哈希表的value值应该是字符c最后一次出现的索引，
而我们要的就是找到这两个字符谁的索引小，所以可以直接对其value形成的list进行排序，取第一个即可。