159. 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.

Thoughts

count: count # of distinct characters

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int left = 0, right = 0, count = 0, len = 0;
        unordered_map <char, int> map;

        while(right < s.length()){
            // put, check new 
            if(++map[s[right]] == 1) count++;
            right++;

            // move left to reduce the window size if 
            // there are more than two distinct chars in the current window
            while(count > 2){
                if(--map[s[left]] == 0) count--;
                left++;
            }
            len = max(len, right - left);
        }

        return len;
    }
};

template

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> map(128,0);
        int cnt = 0, slow = 0 , fast = 0, d = 0;
        while (fast < s.size()){
            if(map[s[fast++]]++ == 0) cnt ++;
            while(cnt > 2) if(map[s[slow++]]-- == 1) cnt--; // after subtraction is 0
            d = max(d, fast - slow);
        }
        return d;
    }
};

results matching ""

    No results matching ""