LeetCode 159题：如何找到只包含最多两个不同字符的最长连续子串？
- 内容介绍
- 文章标签
- 相关推荐
本文共计899个文字，预计阅读时间需要4分钟。
159. 寻找包含两个不同字符的最长子串；知识点：字符串；滑动窗口；题目描述：给定一个字符串s，找出一对最长的、包含两个不同字符的子串，并返回该子串。可以使用一个滑动窗口来解决这个问题。设定一个字符串s+，将其与s拼接，这样当滑动窗口遇到重复字符时，可以通过比较s+中相同位置的两个字符来判断。具体步骤如下：
1. 创建一个长度为256的数组counts，用于记录每个字符的出现次数。
2.初始化左右指针left和right，将right指向字符串s的末尾，left指向字符串s的开始。
3.在右指针右移时，增加counts中相应字符的计数。
4.当counts中两个字符的计数都大于1时，将左指针右移，减少counts中相应字符的计数，直到找到满足条件的子串。
5.每次找到满足条件的子串，比较其长度与当前记录的最长子串长度，如果更长，则更新记录。
6.返回记录的最长子串。
159.至多包含两个不同字符的最长子串题目描述知识点：字符串；滑动窗口
给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入: "eceba"
输出: 3
解释: t 是 "ece"，长度为3。
示例 2:
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为5。
解法一：滑动窗口
这其实也是滑动窗口的一道典型题目
刚看题目，最长子串，其实应该自然的想到滑动窗口。 最大，往往都是right向右移动寻找最优解，然后破坏了条件，然后left移动，缩小窗口，继续形成可行解；
对应到这道题目：
1.right右移，试图寻找一个最长窗口，直至破坏了条件，也就是包含了第三个字符
步骤一我们需要在窗口内含有第三个字符的时候停下来，自然想到了哈希表，当哈希表长度为3的时候，证明第三个字符出现了，这时候就需要去移动左窗口了
2.left开始移动，缩小窗口
left移动到哪个位置呢？我们的目的是让left移动后窗口重新满足条件，也就是只有两个字符，所以需要把一个字符移出去，也就是移到索引最小的位置+1处
例如例1，需要移动到c后面，而不能移动到第2个e后面，所以哈希表的value值应该是字符c最后一次出现的索引，而我们要的就是找到这两个字符谁的索引小，所以可以直接对其value形成的list进行排序，取第一个即可。
在这个过程中不断的更新最大窗口值
class resolution:
def getlongestsubstring(self, s):
hashtable = {}
max_len = left = 0
for i, cur_str in enumerate(s):
if len(hashtable) < 3:
hashtable[cur_str] = i
if len(hashtable) == 3:
index = sorted(hashtable.values())[0] # 在哈希表里的最小索引，left移动，将这个字符移出窗口
left = index + 1
hashtable.pop(s[index]) # 移出哈希表
max_len = max(max_len, i-left+1)
return max_len
本文共计899个文字，预计阅读时间需要4分钟。
159. 寻找包含两个不同字符的最长子串；知识点：字符串；滑动窗口；题目描述：给定一个字符串s，找出一对最长的、包含两个不同字符的子串，并返回该子串。可以使用一个滑动窗口来解决这个问题。设定一个字符串s+，将其与s拼接，这样当滑动窗口遇到重复字符时，可以通过比较s+中相同位置的两个字符来判断。具体步骤如下：
1. 创建一个长度为256的数组counts，用于记录每个字符的出现次数。
2.初始化左右指针left和right，将right指向字符串s的末尾，left指向字符串s的开始。
3.在右指针右移时，增加counts中相应字符的计数。
4.当counts中两个字符的计数都大于1时，将左指针右移，减少counts中相应字符的计数，直到找到满足条件的子串。
5.每次找到满足条件的子串，比较其长度与当前记录的最长子串长度，如果更长，则更新记录。
6.返回记录的最长子串。
159.至多包含两个不同字符的最长子串题目描述知识点：字符串；滑动窗口
给定一个字符串 s ，找出 至多 包含两个不同字符的最长子串 t 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入: "eceba"
输出: 3
解释: t 是 "ece"，长度为3。
示例 2:
输入: "ccaabbb"
输出: 5
解释: t 是 "aabbb"，长度为5。
解法一：滑动窗口
这其实也是滑动窗口的一道典型题目
刚看题目，最长子串，其实应该自然的想到滑动窗口。 最大，往往都是right向右移动寻找最优解，然后破坏了条件，然后left移动，缩小窗口，继续形成可行解；
对应到这道题目：
1.right右移，试图寻找一个最长窗口，直至破坏了条件，也就是包含了第三个字符
步骤一我们需要在窗口内含有第三个字符的时候停下来，自然想到了哈希表，当哈希表长度为3的时候，证明第三个字符出现了，这时候就需要去移动左窗口了
2.left开始移动，缩小窗口
left移动到哪个位置呢？我们的目的是让left移动后窗口重新满足条件，也就是只有两个字符，所以需要把一个字符移出去，也就是移到索引最小的位置+1处
例如例1，需要移动到c后面，而不能移动到第2个e后面，所以哈希表的value值应该是字符c最后一次出现的索引，而我们要的就是找到这两个字符谁的索引小，所以可以直接对其value形成的list进行排序，取第一个即可。
在这个过程中不断的更新最大窗口值
class resolution:
def getlongestsubstring(self, s):
hashtable = {}
max_len = left = 0
for i, cur_str in enumerate(s):
if len(hashtable) < 3:
hashtable[cur_str] = i
if len(hashtable) == 3:
index = sorted(hashtable.values())[0] # 在哈希表里的最小索引，left移动，将这个字符移出窗口
left = index + 1
hashtable.pop(s[index]) # 移出哈希表
max_len = max(max_len, i-left+1)
return max_len