Saturday, February 7, 2015

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.
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char,int> mp;
        int start=0;
        int end = 0;
        int max_len=0;
        int count=0;
        while(end<s.size())
        {
            if (count<2)
            {
                if (mp.find(s[end])==mp.end() || mp[s[end]]<start)
                {
                    count++;
                }
                mp[s[end]]=end;
            }
            else
            {
                if (mp.find(s[end])==mp.end()|| mp[s[end]]<start)
                {
                    count++;
                    while(count>2)
                    {
                        if (mp[s[start]]<=start)
                        {
                            mp.erase(s[start]);
                            count--;
                        }
                        start++;
                    }
                }
                mp[s[end]]=end;
            }
            end++;
            if (count<=2)
            {
                max_len = max(max_len,end-start);
            }
        }
        return max_len;
    }
};

No comments:

Post a Comment