题目描述

给定一个字符串。
请找出最长的连续子串，满足最多包含2个不同字符。

样例1

输入："eceba"
输出：3

解释：最多包含2个不同字符的子串是 "ece"，长度是3。

样例2

输入："ccaabbb"
输出：5

解释：最多包含2个不同字符的子串是 "aabbb"，长度是5。

算法

(双指针扫描) $O(n)$

用两个指针 $i,j(j \lt i)$ 扫描整个字符串。
用哈希表统计 $s[j … i]$ 中每种字符的个数；用一个变量 $d$ 记录 $s[j…i]$ 中不同字符的个数。
每次让指针 $i$ 往后移一位，如果遇到新字符，则让 $d$ 加1；同时更新哈希表。
然后不断往后移动指针 $j$，直到区间 $[j,i]$ 中不同字符的个数不大于2为止。

时间复杂度分析：两个指针均最多从 0 循环到 $n-1$，所以时间复杂度是 $O(n)$。

C++ 代码

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