[Leetcode] 159. Longest Substring with At Most Two Distinct Characters 解题报告，leetcodelongest

[Leetcode] 159. Longest Substring with At Most Two Distinct Characters 解题报告，leetcodelongest

题目：

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.

思路：

这道题目也是典型的two pointers：我们定义一个哈希表来表示不同字符的个数，并设定两个索引点start和end，然后从前往后扫描：一旦发现一个新字符，就把它加入哈希表中，并且判断此时哈希表的大小是否超过2，如果超过则更新start的值，直到哈希表的大小不超过2。每次加入一个字符后，都需要更新一下最大长度，最后返回最大长度即可。虽然算法中出现了两重while循环，但我们说时间复杂度依然是O(n)（请思考是为什么？）。关于空间复杂度，由于哈希表的大小最大的时候为3，所以该算法的空间复杂度实际是O(1）。理论上，这里的时间复杂度和空间复杂度肯定已经是最优的了。

代码：

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> hash;
        int max_length = 0;
        int start = 0, end = 0;
        while (end < s.length()) {
            hash[s[end]]++;
            while (hash.size() > 2) {
                hash[s[start]]--;
                if (hash[s[start]] == 0) {
                    hash.erase(s[start]);
                }
                ++start;
            }
            max_length = max(max_length, end - start + 1);
            ++end;
        }
        return max_length;
    }
};