LeetCode 159. 至多包含两个不同字符的最长子串
题目描述
给定一个字符串 s，返回其中至多包含两种不同字符的最长子串的长度。
示例 1：
输入：s = "eceba"
输出：3
解释：最长子串是 "ece"，长度为 3。
示例 2：
输入：s = "ccaabbb"
输出：5
解释：最长子串是 "aabbb"，长度为 5。
提示：
1 <= s.length <= 10^5-
s由英文字母组成。
题意分析
在由英文字母组成的字符串中，找出至多包含两种不同字符的最长连续子串，返回长度。允许同一种字符重复出现，也允许只有一种字符；限制的是字符种类数，不是字符总数。
子串必须连续，因此可以用左右边界维护一个区间。向右加入字符后，只有出现第三种字符才需要缩小窗口；缩小到重新合法时，再比较这个区间的长度。
解法：滑动窗口维护字符频次
核心思路
[!blue]
用
[left, right]表示当前窗口，用频次表count保存窗口内每个字符的出现次数。表中只保留次数大于零的键，因此键的数量就等于当前字符种类数。右边界每次前进一格，把新字符次数加一。若种类数仍不超过两种，窗口合法；若出现第三种，就不断移走左端字符，并让左边界右移，直到只剩至多两种字符。
移走某个字符的一次出现，不代表这一种字符已经离开窗口。必须先减次数，只有次数降为零时才删除键；否则窗口里仍有同种字符，种类数不应减少。这也是不能只用集合记录出现与否的原因。
为什么左边界无需回退？一个区间已经包含三种字符后，继续向右加入元素不可能让种类变少，所以之前判定不合法的更早起点，以后也不会重新合法。当前只收缩到首次恢复合法的位置，得到的便是以这个右端点结尾的最长合法窗口。
每个子串都有一个右端点，依次枚举所有右端点并保存最大窗口长度，就能覆盖全局最优答案。每轮开始时至多两种字符，新增一个字符后最多暂时出现三种，所以频次表始终只需保存常数个键。
解题步骤
- 初始化
left = 0、答案best = 0和空频次表。- 从左到右枚举
right，增加当前字符的出现次数。- 当键数超过
2时，减少左端字符的次数；减到零则删除键，并推进left。- 窗口恢复合法后，用
right - left + 1更新答案。- 扫描结束返回
best。
代码实现
class Solution {
public int lengthOfLongestSubstringTwoDistinct(String s) {
Map<Character, Integer> count = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
char current = s.charAt(right);
count.put(current, count.getOrDefault(current, 0) + 1);
while (count.size() > 2) {
char removed = s.charAt(left++);
int remaining = count.get(removed) - 1;
// 只有频次归零才删除键，表大小才能准确表示当前字符种类。
if (remaining == 0) {
count.remove(removed);
} else {
count.put(removed, remaining);
}
}
// 恢复到至多两种字符后，当前窗口才能参与最长长度比较。
best = Math.max(best, right - left + 1);
}
return best;
}
}
func lengthOfLongestSubstringTwoDistinct(s string) int {
count := make(map[byte]int)
left, best := 0, 0
for right := 0; right < len(s); right++ {
count[s[right]]++
for len(count) > 2 {
removed := s[left]
count[removed]--
// 只有频次归零才删除键，表大小才能准确表示当前字符种类。
if count[removed] == 0 {
delete(count, removed)
}
left++
}
// 恢复到至多两种字符后，当前窗口才能参与最长长度比较。
if length := right - left + 1; length > best {
best = length
}
}
return best
}
复杂度分析
- 时间复杂度：期望 $O(n)$，左右端点总移动次数为线性，哈希操作期望常数时间。
- 空间复杂度：$O(1)$，调整时最多临时保存三个字符键。
关键点总结
[!green]
- “至多两种”具有窗口单调性：加入字符可能失效，移除字符只会更容易合法。
- 扩张后先收缩到合法，再更新最长长度。
- 哈希表大小表示字符种类数，前提是计数归零时立即删除键。
- 将常数 2 替换为
k，就是“至多包含 K 个不同字符”的通用模板。
易错点总结
[!yellow]
- 计数降为 0 后不删除键，会让字符种类数一直偏大。
- 收缩条件写成
>= 2会把合法的两种字符窗口也缩掉。- 在窗口尚有三种字符时更新答案，会把非法区间计入。
- 使用集合而不是频次表，移出一个重复字符时会过早删除该字符。
- 窗口长度是
right - left + 1，不要漏掉 1。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 3. 无重复字符的最长子串 | 中等 | 同样维护字符窗口，原题禁止任何重复，本题允许重复但种类最多两种。 |
| 340. 至多包含 K 个不同字符的最长子串 | 中等 | 把允许的字符种类从2推广到k，频次归零时减少种类数的窗口逻辑相同。 |
| 904. 水果成篮 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题允许最多两种字符，该题把两种水果限制转为两类元素窗口。 |
| 1100. 长度为 K 的无重复字符子串 | 中等 | 用滑动窗口维护字符频次和有效左边界；本题允许最多两种字符，该题固定窗口长度后统计无重复窗口。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！