0159. Longest Substring with At Most Two Distinct Characters ============================================================ 题目信息 -------- :题号: 0159. 至多包含两个不同字符的最长子串 :难度: Medium :主题: 字符串、滑动窗口、频次表、双指针 :原题: `LeetCode 0159 `_ :重点: 维护至多两个字符的最长可行窗口,第三种字符进入时只删除必要的左前缀,并用频次归零判断种类消失 题目重述 -------- 给定字符串 ``s``,返回其中至多包含两种不同字符的最长连续子串长度。子串必须在原字符串中连续;同一字符 可以出现任意多次。空字符串返回 ``0``。 自建示例 -------- * ``s = "eceba"``:最长合法子串为 ``"ece"``,包含 ``e``、``c`` 两种字符,返回 ``3``; * ``s = "ccaabbb"``:``"aabbb"`` 长度为 ``5``,只含 ``a``、``b``; * ``s = "aaaa"``:整串只有一种字符,返回 ``4``; * ``s = ""``:没有非空子串,返回 ``0``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int expandFromEveryStart(const std::string& s) { int bestLength = 0; for (int start = 0; start < static_cast(s.size()); ++start) { std::unordered_map frequency; for (int end = start; end < static_cast(s.size()); ++end) { ++frequency[s[end]]; if (frequency.size() > 2) { break; } bestLength = std::max( bestLength, end - start + 1 ); } } return bestLength; } int keepLongestValidWindow(const std::string& s) { std::unordered_map frequency; int left = 0; int bestLength = 0; for (int right = 0; right < static_cast(s.size()); ++right) { ++frequency[s[right]]; while (frequency.size() > 2) { const char removed = s[left]; ++left; --frequency[removed]; if (frequency[removed] == 0) { frequency.erase(removed); } } bestLength = std::max( bestLength, right - left + 1 ); } return bestLength; } public: int lengthOfLongestSubstringTwoDistinct(std::string s) { return keepLongestValidWindow(s); } }; 题解 ---- 原始方案:为每个左端重新扩张 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 固定 ``start`` 后向右加入字符,并用频次表统计种类;一旦出现第三种字符,更长的同起点子串也都会非法, 可以停止当前扩张。``expandFromEveryStart`` 已经利用了这个单调性,但相邻起点会重复统计大片重叠区域。 例如只有两种字符的长字符串,每个起点都能扫描到末尾,时间仍为 ``O(n^2)``。 当右端继续前进时,旧窗口中的字符统计并没有失效。与其换一个起点从头计算,不如保留窗口,只在约束被 破坏时移动左端删除必要字符。 窗口状态必须保存频次而不只是字符集合 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 令当前窗口为闭区间 ``[left, right]``,频次表精确记录其中每个字符的出现次数。右端字符加入后,若种类数 不超过二,窗口仍合法;若出现第三种,就逐个移出左端字符,直到某个字符频次降为零并从表中删除,种类数 重新变为二。 只保存“当前见过哪些字符”不够,因为移走一个字符实例不代表这个字符已经离开窗口。例如 ``"ece"`` 左端 移出第一个 ``e`` 后,右侧仍有另一个 ``e``;只有计数从一降到零时,才应减少不同字符数。 为什么只移动左端不会漏掉更优答案 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 固定右端 ``right`` 时,若窗口含三种字符,任何比当前 ``left`` 更靠左的起点只会包含更多字符,也必然非法; 因此只能右移左端。收缩到种类数首次回到二时,当前 ``left`` 是这个右端下最靠左的合法起点,窗口就是以 ``right`` 结尾的最长合法子串。用它更新全局最大值即可覆盖每个可能右端的最优候选。 被左端永久移出的字符也无需将来重新加入旧位置:后续右端只会更靠右,任何包含这些旧位置的窗口若已经因 第三种字符非法,不可能通过增加更多字符重新合法。两个指针都只向右移动。 具体走读 ``eceba`` ~~~~~~~~~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 新右端 - 加入后状态 - 收缩与合法窗口 * - ``e``,下标 ``0`` - ``{e:1}`` - ``"e"``,长度 ``1`` * - ``c``,下标 ``1`` - ``{e:1,c:1}`` - ``"ec"``,长度 ``2`` * - ``e``,下标 ``2`` - ``{e:2,c:1}`` - ``"ece"``,长度 ``3`` * - ``b``,下标 ``3`` - 出现第三种 ``{e:2,c:1,b:1}`` - 移出 ``e`` 后仍三种,再移出 ``c``;窗口为 ``"eb"`` * - ``a``,下标 ``4`` - ``{e:1,b:1,a:1}`` - 依次移出 ``e``,窗口为 ``"ba"`` 在处理 ``b`` 时,第一个 ``e`` 被移出后计数仍为一,不能提前删除 ``e`` 键;继续移出唯一的 ``c`` 后才 恢复两种字符。 更新顺序与空串边界 ~~~~~~~~~~~~~~~~~~ 必须先完成 ``while`` 收缩,再用 ``right-left+1`` 更新答案;在第三种字符仍存在时更新会把非法窗口计入。 空串的右端循环不执行,``bestLength`` 保持零。频次表使用 ``char`` 为键,不依赖固定字母表大小,也无需为 某种字符编码单独开数组。 正确性与复杂度 ~~~~~~~~~~~~~~ 每轮结束时频次表与窗口内容一致、种类数至多二,且对当前右端窗口尽可能长;因此所有记录长度都合法,每个 右端的最佳合法候选又都被检查,全局最大值正确。右指针访问每个字符一次,左指针也最多移出每个字符一次, 总时间 ``O(n)``,不是嵌套循环表面上的二次方。频次表在收缩完成后最多含两个键,工作空间 ``O(1)``; 逐起点基线最坏 ``O(n^2)``。