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.

 

可与对照看。

 

这个题很显然使用双指针进行遍历的，begin与end之间的窗口代表符合要求的字符子串。

解法一：

inWindow数组保存窗口中的两个不同字符。（若找不到两个不同的字符，直接返回字符串长度）

map<char, int>保存inWindow中两个字符在窗口中的出现次数。

判断新字符的标准为不等于inWindow数组的任一字符，那么就需要收缩begin，直到inWindow腾出空间给新字符。

class Solution {  public:    int lengthOfLongestSubstringTwoDistinct(string s)     {        if(s == "")            return 0;        else if(s.size() <= 2)            return s.size();        //slip window [begin, end]        //initial the window with two different chars        int size = s.size();        int begin = 0;        int end = 1;        while(end < size && s[end] == s[begin])            end ++;        //to here, end == size or s[end] != s[begin]        if(end == size)            return size;    //all chars are the same        char inWindow[2] = {s[begin], s[end]};        map
     
       m;    //char->count map        m[s[begin]] = end-begin;    //[begin,end) are all s[begin]        m[s[end]] = 1;        int longest = end-begin+1;        end ++;        while(end < size)        {            m[s[end]] ++;            if(s[end] == inWindow[0] || s[end] == inWindow[1])            //in window, extend end                longest = max(longest, end-begin+1);            else            {
    //not in window, shrink begin                //remove a char from window                while(m[inWindow[0]] != 0 && m[inWindow[1]] != 0)                {                    m[s[begin]] --;                    begin ++;                }                //to here, either m[inWindow[0]] == 0 or m[inWindow[1]] == 0                if(m[inWindow[0]] == 0)                    inWindow[0] = s[end];                else                    inWindow[1] = s[end];            }            end ++;        }        return longest;    }};
     

 

解法二：

由于A~Z,a~z的ASCII码不超过122，因此开辟128的数组record进行窗口中每个字符的计数。

再设置计数位count，记录当前窗口中有多少个不同的字符。

判断新字符的标准为record值为1（加入新字符之后）。

如果count>2，那么就需要收缩begin，直到s[begin]对应的计数为0，代表少了一类字符，count--

class Solution {  public:    int lengthOfLongestSubstringTwoDistinct(string s)     {        if(s.size() <= 2)            return s.size();        int size = s.size();        int record[128] = {
   0};    //record the appearance times of each char. Note 'z' is 122, 128 is enough.        int begin = 0;        int end = 0;        int count = 0;    //distinct count        int longest = 0;        while(end < size)        {            record[s[end]] ++;            if(record[s[end]] == 1)            //new char                count ++;            while(count > 2)            {
    //shrink                record[s[begin]] --;                if(record[s[begin]] == 0)                    count --;                //remove one char                begin ++;            }            longest = max(longest, end-begin+1);            end ++;        }        return longest;    }};

 

我编写的测试用例如下，上述两个解法代码全部通过。

int main(){        string str1 = "";                //expect: 0 ""    string str2 = "a";                //expect: 1 "a"    string str3 = "aa";                //expect: 2 "aa"    string str4 = "aba";            //expect: 3 "aba"    string str5 = "abcd";            //expect: 2 "ab"    string str6 = "abcdedcba";        //expect: 3 "ded"    string str7 = "abbcdededcba";    //expect: 5 "deded"    string str8 = "eceba";            //expect: 3 "ece"    string str9 = "abaece";            //expect: 3 "aba"    string str10 = "ababcd";        //expect: 4 "abab"    string str11 = "cababcd";        //expect: 4 "abab"    string str12 = "abcdefgabcdefg";//expect: 2 "ab"    string str13 = "ababababababab";//expect: 14 "ababababababab"    Solution s;    cout << s.lengthOfLongestSubstringTwoDistinct(str1) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str2) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str3) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str4) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str5) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str6) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str7) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str8) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str9) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str10) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str11) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str12) << endl;    cout << s.lengthOfLongestSubstringTwoDistinct(str13) << endl;}