Thursday, March 5, 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) {
        int len=0;
        unordered_map<char,int> mp;
        int count=0;
        int start=0,end=0;
        while(end<s.size())
        {
            if (mp.find(s[end])==mp.end())
            {
                if (count<2)
                {
                    mp[s[end]]=end;
                    count++;
                }
                else
                {
                    count++;
                    while(count>2)
                    {
                        if (mp.find(s[start])!=mp.end())
                        {
                            if (mp[s[start]]==start)
                            {
                                mp.erase(s[start]);
                                count--;
                            }
                        }
                        start++;
                    }
                    mp[s[end]]=end;
                }
            }
            else
            {
                mp[s[end]]=end;
            }
            len = max(len,end-start+1);
            end++;
        }
        return len;
    }
};

No comments:

Post a Comment