C++实现LeetCode 159：最多两个不同字符的最长子串

Oliver

发布时间：2026-10-16 | 7人浏览过

原创

本文详细解析如何使用C++解决LeetCode第159题，即在字符串中寻找包含最多两个不同字符的最长连续子串。文章提供了基于哈希表、坐标映射、双指针及纯变量优化的四种解法，均属于高效的滑动窗口算法。

题目解析与核心思路

给定一个字符串 s，目标是找到包含最多 2 种不同字符的最长子串 t 的长度。例如输入 "eceba"，最长的满足条件的子串为 "ece"，长度为 3；输入 "ccaabbb"，最长子串为 "aabbb"，长度为 5。

解决此类“最长/最短满足条件子串”问题的通用方法是滑动窗口（Sliding Window）。我们需要维护一个窗口 [left, right]，确保窗口内的不同字符数量不超过限制（本题为 2）。如果超过限制，则移动左指针缩小窗口。

解法一：基于计数的滑动窗口

这是最直观的滑动窗口实现方式。使用哈希表记录窗口内每个字符出现的次数。

扩大窗口：遍历字符串，将当前字符加入哈希表并增加计数。
缩小窗口：当哈希表中键的数量（即不同字符数）超过 2 时，循环移动左指针：
- 减少左指针所指字符的计数。
- 若计数减至 0，从哈希表中移除该字符。
- 左指针右移。
更新结果：在每次循环中，计算当前窗口长度并更新最大值。

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, left = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++i) {
            ++m[s[i]];
            while (m.size() > 2) {
                if (--m[s[left]] == 0) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

解法二：记录最新坐标的滑动窗口

为了加速删除最左侧的字符，可以将哈希表中的值改为字符最后一次出现的索引。这样可以直接定位到需要删除的那个字符。

存储坐标：遍历时直接更新 m[s[i]] = i。
定位删除：当字符数超过 2 时，检查 m[s[left]]。如果它等于当前的 left，说明这是该字符最后一次出现，将其从哈希表删除。
移动左指针：无论是否删除，左指针都向右移动。

这种方法逻辑清晰，便于理解如何“精准”剔除旧字符。

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, left = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < s.size(); ++i) {
            m[s[i]] = i;
            while (m.size() > 2) {
                if (m[s[left]] == left) m.erase(s[left]);
                ++left;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

解法三：双指针跳跃式搜索

此方法适用于限定为 2 个不同字符的特例。我们维护两个指针，left 指向窗口起始位置，right 指向窗口中第二个不同字符最后一次出现的位置前一位。

跳过重复：若当前字符与前一个相同，直接继续，无需操作。
检测新字符：若不同且不是第一个字符，则判断其是否与 right 指向的字符相同。
更新逻辑：
- 若相同：保持窗口，准备下一步。
- 若不同：当前窗口结束，计算长度 i - left，并将 left 跳转到 right + 1，同时 right 更新为 i - 1。

注意：由于最后几个字符可能与窗口末尾字符相同导致未触发 while 或更新逻辑，返回时需比较 res 和 s.size() - left。

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int left = 0, right = -1, res = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) continue;
            if (right >= 0 && s[right] != s[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
        }
        return max(s.size() - left, res);
    }
};

解法四：空间最优的变量控制

既然只需区分两个字符，我们可以不使用哈希表，而是用变量记录状态。这能将空间复杂度降为 O(1)。

first, second: 记录窗口内的两个不同字符。
cntLast: 记录最后一个被切换到的字符（即 second）的连续长度。
cur: 当前子串的总长度。

遍历逻辑：

若遇到 first 或 second，当前长度 cur 自增。
若遇到新字符：
- 原 first 被挤出窗口，窗口变为以 second 和新字符开头。
  - 更新 cur = cntLast + 1（因为之前的部分是旧的）。
- 更新计数：若当前字符等于 second，cntLast 自增；否则重置为 1（因为刚换的新字符只有一个）。
- 角色更替：first = second, second = 新字符。

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int res = 0, cur = 0, cntLast = 0;
        char first, second;
        for (char c : s) {
            // 如果是已知的字符，长度+1；如果是新字符，长度变为上一个连续段的长度+1
            cur = (c == first || c == second) ? cur + 1 : cntLast + 1;
            // 更新lastCount：如果当前是second字符，连续长度加1，否则重置为1
            cntLast = (c == second) ? cntLast + 1 : 1;
            // 只要不是second，就意味着发生了轮换（要么是新轮换进second，要么是重置second）
            if (c != second) {
                first = second; 
                second = c;
            }
            res = max(res, cur);
        }
        return res;
    }
};