Problem description:

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

Example 1:

Input: “eceba”
Output: 3
Explanation: t is “ece” which its length is 3.
Example 2:

Input: “ccaabbb”
Output: 5
Explanation: t is “aabbb” which its length is 5.

Solution:

This question belong to the same category as those such as “longest substring without repeating characters”, “minimum window substring”, and “substring with concatenation of all words”. To solve this kind of question we can use two pointers and a hash table. When the key of the hash table is char, we can simply use an array as the hash table. The most important idea in solving this kind of questions is how to update the start pointer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        start, end = 0, 0
        res = 0
        dic = defaultdict(int)
        
        for end in range(len(s)):
            dic[s[end]] += 1
            
            while len(dic) > 2:
                dic[s[start]] -= 1
                if dic[s[start]] == 0:
                    del dic[s[start]]
                start += 1
            if not res or res < (end-start+1):
                res = end-start+1
            # if not res or len(res) < len(s[start:end+1]):
            #     res = s[start:end+1]
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
        
    }
};

Solution2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int left = 0, right = -1, res = 0;
        for (int i = 1; i < s.length(); ++i) {
            if (s[i] == s[i - 1]) continue; //current position character is the same as previous one
            if (right >= 0 && s[right] != s[i]) {
                res = max(res, i - left);
                left = right + 1;
            }
            right = i - 1;
            //1. first time would be have two different character
            //2. after that, j means: when see different character, then move the end pointer j to previous substring
        }
        return max(int(s.length()) - left, res);
    }
}

Solution 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        /*
        idea: use a map to track how many distinct characters we have right now.
              two pointers to traverse the whole string, adding/subtracting the result length
        
        two pointers, start and end. 
        end: to traverse the whole string, increasing the length
        start: if we have two distinct chars, use start to substract the length
        */
        unordered_map<char, int> map;
        int start= 0, end= 0, res= 0, count= 0;
        while(end< s.length()){
            char send= s[end];
            map[send]++;
            if(map[send] == 1)
                count++;
            end++;
            
            while(count > 2){
                char stmp= s[start];
                map[stmp]--;
                if(map[stmp] == 0)
                    count--;
                start++;
            }
            res= max(res, end-start);
        }
        return res;
    }
};

time complexity: $O(n)$
space complexity: $O(n)$