159. Longest Substring with At Most Two Distinct Characters (Hard)

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

Solution 1: Hash Table 13ms

这道题给我们一个字符串，让我们求最多有两个不同字符的最长子串。那么我们首先想到的是用哈希表来做，哈希表记录每个字符的出现次数，然后如果哈希表中的映射数量超过两个的时候，我们需要删掉一个映射，比如此时哈希表中e有2个，c有1个，此时把b也存入了哈希表，那么就有三对映射了，这时我们的left是0，先从e开始，映射值减1，此时e还有1个，不删除，left自增1。这是哈希表里还有三对映射，此时left是1，那么到c了，映射值减1，此时e映射为0，将e从哈希表中删除，left自增1，然后我们更新结果为i - left + 1，以此类推直至遍历完整个字符串，参见代码如下：

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> m;
        int start = 0, res = 0;
        for (int i = 0; i < s.size(); ++i) {
            ++m[s[i]];
            // discint k has been reached, cannot add new characters
            while (m.size() > 2) {
                // remove the one char in current substring
                if (--m[s[start]] == 0) m.erase(s[start]);
                ++start;
            }
            res = max(res, i-start+1);
        }

        return res;
    }
};

Solution 2: Hash Table 13ms

我们除了用哈希表来映射字符出现的个数，我们还可以映射每个字符最新的坐标，比如题目中的例子"eceba"，遇到第一个e，映射其坐标0，遇到c，映射其坐标1，遇到第二个e时，映射其坐标2，当遇到b时，映射其坐标3，每次我们都判断当前哈希表中的映射数，如果大于2的时候，那么我们需要删掉一个映射，我们还是从left=0时开始向右找，我们看每个字符在哈希表中的映射值是否等于当前坐标left，比如第一个e，哈希表此时映射值为2，不等于left的0，那么left自增1，遇到c的时候，哈希表中c的映射值是1，和此时的left相同，那么我们把c删掉，left自增1，再更新结果，以此类推直至遍历完整个字符串，参见代码如下：

int lengthOfLongestSubstringTwoDistinct(string s) {
    int res = 0, start = 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[start]] == start) {
                m.erase(s[start]);
            }
            ++start;
        }
        res = max(res, i-start+1);
    }
    return res;
}

Solution 3: Two Pointers 3ms

i: always points to the start of substring

j: points to the last occurrence of the 1st character.

If we have encountered 2 distinct characters and then see 3rd new character, we need to check if the 1st and 3rd characters are the same. If not, we move i to j+1 (now becomes the first char). If yes, not need to change.

Then move j to the last occurrence of 2nd character.

int lengthOfLongestSubstringTwoDistinct(string s) {
    int i = 0, j = -1, res = 0;
    for (int k = 1; k < s.size(); ++k) {
        if (s[k] == s[k-1]) continue;
        if (j > -1 && s[k] != s[j]) {
            res = max(res, k-i);
            i = j+1;
        }
        j = k-1;
    }
    return max(res, (int)s.size()-i);
}

Solution 4: Hash Table, Two Pointers 3ms

Substring problem template

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128, 0);
        int count = 0, left = 0, right = 0, len = 0;
        while (right < s.size()) {
            if (map[s[right++]]++ == 0) ++count;
            while (count > 2) {
                if (--map[s[left++]] == 0) --count;
            }
            len = max(len, right-left);
        }
        return len;
    }
};