LeetCode 159. 至多包含两个不同字符的最长子串

2024-09-04 HGNULB 约 6 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 159. 至多包含两个不同字符的最长子串

题意分析

给一个字符串，求出其中最长的一段连续字符，要求这一段里出现的不同字符种类不超过 2 种，返回它的长度。注意返回的是长度而不是子串本身，也不要求恰好两种——只有一种字符同样合法。

「连续」这两个字决定了候选答案只有 $O(n^2)$ 个区间，每个区间由起点和终点唯一确定。这和子序列题是两条完全不同的路，一旦看成子序列，"eceba" 里的 e、e、c 就会被错误地拼在一起。

真正的算法信号藏在「至多」里：如果一个区间满足「不同字符不超过 2 种」，那么它的任意子区间也一定满足；反过来，一旦某个区间违反了条件，把它继续向右扩张只会更糟。这种「合法性对区间包含关系单调」的性质，意味着当右端点固定时，所有合法的左端点构成一段连续的后缀，于是左端点只需要单向前进、永远不用回头。

字符集方面题目没有特别限制，可能是任意 ASCII 甚至 Unicode 字符，所以更稳妥的做法是按字符做计数映射，而不是写死一个 26 长度的数组。

边界有几种：空串返回 0；整串只有一种字符时答案是全长；串长本身不超过 2 时答案就是串长；还有一个隐蔽的边界——当左端点向右移动导致某个字符在区间里彻底消失时，「种类数」这个统计量必须同步减少，否则后面的所有判断都会失真。

解法：滑动窗口维护字符频次

核心思路

用滑动窗口维护一个始终至多包含两种字符的区间 [left, right]。右指针负责加入新字符；若窗口中的字符种类超过 2，就移动左指针并减少对应频次，直到窗口重新合法。

能使用滑动窗口的原因是约束具有单调性：合法窗口加入新字符后可能失效，但从左侧删除字符只会减少或保持种类数，不可能让它更不合法。因此左指针无需回退，避免了枚举所有子串的 $O(n^2)$ 开销。

窗口合法时，它是当前右端点下能够保留的最长候选区间，因此用 right - left + 1 更新答案。左右指针都只向右移动，不会回退。

频次表不仅要记录字符是否出现，还要记录出现次数：左端移走一个字符后，只有计数降为 0 才能删除该键。哈希表的键数就是窗口内不同字符的数量。

每轮收缩结束后的不变量是：窗口至多包含两种字符，并且当前 left 是本轮恢复合法时的最早位置。于是该窗口就是以 right 结尾的最长合法候选；枚举所有右端点后，全局最大值不会遗漏。

解题步骤

初始化左指针 left = 0、答案 best = 0 和空频次表。

依次移动右指针，将当前字符计数加一。

当频次表大小超过 2 时，移出左端字符；计数为 0 时删除键，然后右移 left。

窗口恢复合法后，用当前长度更新最大值。

例如 "eceba"：窗口扩张到 "ece" 时含 e、c 两种字符，长度为 3；加入 b 后出现第三种字符，左端收缩到 "eb"，最终答案仍为 3。

代码实现

import java.util.HashMap;
import java.util.Map;

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(C)$，其中 C 是字符集大小；窗口调整过程中哈希表最多短暂保存 3 种字符。固定英文字符集下可视为 $O(1)$。

关键点总结

“至多两种”具有窗口单调性：加入字符可能失效，移除字符只会更容易合法。

扩张后先收缩到合法，再更新最长长度。

哈希表大小表示字符种类数，前提是计数归零时立即删除键。

将常数 2 替换为 k，就是“至多包含 K 个不同字符”的通用模板。

易错点总结

计数降为 0 后不删除键，会让字符种类数一直偏大。

收缩条件写成 >= 2 会把合法的两种字符窗口也缩掉。

在窗口尚有三种字符时更新答案，会把非法区间计入。

使用集合而不是频次表，移出一个重复字符时会过早删除该字符。

窗口长度是 right - left + 1，不要漏掉 1。

相似题目

题目	难度	考察点
340. 至多包含 K 个不同字符的最长子串	中等	本题的直接推广，把常数 2 换成参数 k，代码一字不改地复用
3. 无重复字符的最长子串	中等	相当于 k = 1 的「每种字符至多一个」，可用集合或下标跳跃优化
904. 水果成篮	中等	换成整数数组的同题，两个篮子就是两种不同字符
424. 替换后的最长重复字符	中等	合法性判据改成「区间长度减最高频次不超过 k」，需维护最大频次
1004. 最大连续1的个数 III	中等	判据退化为「区间内 0 的个数不超过 k」，只需一个计数器
992. K 个不同整数的子数组	困难	求「恰好 k 种」的个数，靠「至多 k 种」减「至多 k-1 种」
76. 最小覆盖子串	困难	求最短，答案要在收缩过程中更新，与本题的更新时机正好相反
567. 字符串的排列	中等	区间长度固定，左右指针同步平移，不存在变长收缩
LCR 016. 无重复字符的最长子串	中等	与 3 题同题，可直接套用
剑指 Offer 48. 最长不含重复字符的子字符串	中等	与 3 题同题，可直接套用