[leetcode] Longest Substring with At Most Two Distinct Characters


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. i points to the head of possible string and j points to the tail of it.

Use a hashmap to count the number of appearance of current characters appears in the possible substr.

move i or j depends on the size of map.

if map.size() > 2, move i,

else move j

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> map;
        int i = 0; // head of the possible substr
        int j = 0; // tail of the possible substr
        int ans = 0;
        while(j < s.size()){
            if(map.find(s[j]) != map.end()){
                //s[j] already exists in substr
                map[s[j]] += 1;
                j++;
            }
            else{
                //s[j] not exists in substr before
                while(map.size() > 1){
                    map[s[i]] -= 1;
                    if(map[s[i]] == 0){
                        map.erase(s[i]);
                    }
                    i++;
                }
                //map.size() == 1
                map[s[j]] = 1;
                j++;
            }
            ans = max(ans, j - i);
        }
        return ans;
    }
};

 

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.