Share my c++ solution


  • 56
    M

    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" and the solution to these questions seem usually differ only in this respect.

    int lengthOfLongestSubstringTwoDistinct(string s) {
        if(s.empty()) return 0;
        
        int dict[256]; 
        fill_n(dict,256,0);
        int start = 0, len = 1, count = 0;
        for(int i=0; i<s.length(); i++) {
            dict[s[i]]++;
            if(dict[s[i]] == 1) { // new char
                count++;
                while(count > 2) {
                    dict[s[start]]--;
                    if(dict[s[start]] == 0) count--; 
                    start++;
                }
            }
            if(i-start+1 > len) len = i-start+1;
        }
        return len;
    }

  • 1
    R
        int lengthOfLongestSubstringTwoDistinct(string s) 
        {
            int st = 0, maxL = 0;
            unordered_map<int, int> char2Index;
            for(int i = 0; i < s.size(); ++i)
            {
                if(char2Index.size() <= 2)
                    char2Index[s[i]] = i;
                if(char2Index.size() == 3)
                {
                    maxL = max(maxL, i-st);
                    for(auto it = char2Index.begin(); it != char2Index.end();)
                    {
                        if(it->first != s[i-1] && it->first != s[i])
                        {
                            st = it->second+1;
                            it = char2Index.erase(it);
                            break;
                        }
                        else
                            ++it;
                    }
                }
            }
            maxL = max(maxL, (int)s.size()-st);
            return maxL;
        }

  • 0
    I
    This post is deleted!

  • -1
    I
    int lengthOfLongestSubstringTwoDistinct(string S){
        const int len=S.length();
        if(len<=2)  return len;
        int p1=0, p2=-1, res=2;
        char c1=S[0], c2;
        for(int i=1; i<len; ++i){
            if(S[i]!=S[i-1]){
                if(p2<0){
                    p2=i;
                    c2=S[i];
                }else{
                    if(S[i]!=c1 && S[i]!=c2){
                        p1=p2;
                        p2=i;
                        c1=c2;
                        c2=S[i];
                    }else{
                        if(S[i]!=S[p2])
                            p2=i;
                    }
                }
            }
            res=max(res, i-p1+1);
        }
        return res;
    }

  • 0
    Y

    I try to run your code, it's wrong answer


  • 0
    A

    like your analysis.
    suggestion to improve: it takes O(n) to update the head when the 3rd char is detected. instead of storing counter of a char, you can store the indices in a list, then you can figure out the last occurrence of the char and place new head right after it. this takes O(1).


  • 0
    A
    This post is deleted!

  • 13

    Here is a nice solution using two pointers (without the hash table). I rewrite it in C++ below :-)

    class Solution { 
    public:
        int lengthOfLongestSubstringTwoDistinct(string s) {
            int l = 0, r = -1, len = 0, n = s.length();
            for (int i = 1; i < n; i++) {
                if (s[i] == s[i - 1]) continue;
                if (r >= 0 && s[i] != s[r]) {
                    len = max(len, i - l); 
                    l = r + 1;
                }
                r = i - 1;
            }
            return max(n - l, len);  
        }
    };
    

  • 0

    Very clear explanations and code :-)


  • 0
    C

    Nice solution, it seems that if we change this checking "while(count > 2)" to "while(count > k)", this solution can be extended to "Longest Substring with At Most k Distinct Characters" case.


  • 0
    C

    amazing solution..


  • 0
    T

    Hi,

    Thanks for sharing the solutions. I think you analysis and explanation at the beginning part is great. How did you come up with these ideas? You summarized it by yourself or you found it somewhere else?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.